Ignore:
Timestamp:
Nov 28, 2017, 1:45:19 AM (22 months ago)
Author:
nmedfort
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp

    r5742 r5748  
    2323#include <llvm/Support/raw_ostream.h>
    2424#include <llvm/Support/Format.h>
     25#include <llvm/ADT/SmallVector.h>
    2526
    2627namespace UCD {
     
    2829using bitquad_t = UnicodeSet::bitquad_t;
    2930using run_t = UnicodeSet::run_t;
    30 using interval_t = UnicodeSet::interval_t;
    3131
    3232//
     
    4646SlabAllocator<> UnicodeSet::GlobalAllocator;
    4747
    48 const uint64_t QUAD_BITS = (8 * sizeof(bitquad_t));
    49 const uint64_t MOD_QUAD_BIT_MASK = QUAD_BITS - 1;
    50 const uint64_t UNICODE_QUAD_COUNT = (UNICODE_MAX + 1) / QUAD_BITS;
    51 const bitquad_t FULL_QUAD_MASK = -1;
     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);
    5252
    5353inline run_type_t typeOf(const run_t & run) {
     
    5959}
    6060
     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
    6198/** ------------------------------------------------------------------------------------------------------------- *
    6299 * @brief append_run
    63100 ** ------------------------------------------------------------------------------------------------------------- */
    64 template <class RunVector>
    65 inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) {
     101inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) noexcept {
    66102    if (LLVM_UNLIKELY(length == 0)) {
    67103        return;
     
    76112 * @brief append_quad
    77113 ** ------------------------------------------------------------------------------------------------------------- */
    78 template <class QuadVector, class RunVector>
    79 inline void append_quad(const bitquad_t quad, QuadVector & quads, RunVector & runs) {
     114inline void append_quad(const bitquad_t quad, QuadVector & quads, RunVector & runs) noexcept {
    80115    run_type_t type = Empty;
    81116    if (LLVM_UNLIKELY(quad == 0)) {
    82117        type = Empty;
    83     } else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
     118    } else if (LLVM_UNLIKELY(~quad == 0)) {
    84119        type = Full;
    85120    } else {
     
    96131 * Sanity check for each function that constructs or modifies a UnicodeSet
    97132 ** ------------------------------------------------------------------------------------------------------------- */
    98 template <class RunVector, class QuadVector>
    99 inline bool verify(const RunVector & runs, const QuadVector & quads) {
     133inline bool verify(const run_t * const runs, const uint32_t runLength, const bitquad_t * const quads, const uint32_t quadLength) noexcept {
    100134    unsigned sum = 0;
    101135    unsigned mixedQuads = 0;
    102     for (auto run : runs) {
    103         const auto type = typeOf(run);
     136    for (unsigned i = 0; i < runLength; ++i) {
     137        const auto type = typeOf(runs[i]);
    104138        if (LLVM_UNLIKELY(type != Empty && type != Mixed && type != Full)) {
    105             throw std::runtime_error("illegal run type " + std::to_string(type) + " found");
    106         }
    107         const auto l = lengthOf(run);
     139            llvm::errs() << "illegal run type " << type << " found\n";
     140            return false;
     141        }
     142        const auto l = lengthOf(runs[i]);
    108143        if (LLVM_UNLIKELY(l == 0)) {
    109             throw std::runtime_error("zero-length quad found");
     144            llvm::errs() << "zero-length quad found\n";
     145            return false;
    110146        }
    111147        if (type == Mixed) {
     
    115151    }
    116152    if (LLVM_UNLIKELY(sum != UNICODE_QUAD_COUNT)) {
    117         throw std::runtime_error("found " + std::to_string(sum) + " quads but expected " + std::to_string(UNICODE_QUAD_COUNT));
    118     }
    119     if (LLVM_UNLIKELY(mixedQuads != quads.size())) {
    120         throw std::runtime_error("found " + std::to_string(quads.size()) + " mixed quad but expected " + std::to_string(mixedQuads));
    121     }
    122     for (const auto quad : quads) {
    123         if (LLVM_UNLIKELY(quad == 0)) {
    124             throw std::runtime_error("Empty quad found in Mixed quad array!");
    125         } else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
    126             throw std::runtime_error("Full quad found in Mixed quad array!");
     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;
    127164        }
    128165    }
     
    132169
    133170/** ------------------------------------------------------------------------------------------------------------- *
    134  * @brief empty
    135  ** ------------------------------------------------------------------------------------------------------------- */
    136 bool UnicodeSet::empty() const {
    137     return (mRuns.size() == 1) && typeOf(mRuns.front()) == Empty;
    138 }
    139 
    140 /** ------------------------------------------------------------------------------------------------------------- *
    141  * @brief full
    142  ** ------------------------------------------------------------------------------------------------------------- */
    143 bool UnicodeSet::full() const {
    144     return (mRuns.size() == 1) && typeOf(mRuns.front()) == Full;
    145 }
    146 
    147 /** ------------------------------------------------------------------------------------------------------------- *
    148171 * @brief at
    149172 ** ------------------------------------------------------------------------------------------------------------- */
    150173codepoint_t UnicodeSet::at(const size_type k) const {
    151     auto qi = mQuads.cbegin();
     174
    152175    size_type base = 0;
    153176    size_type remaining = k;
    154     for (const run_t & r : mRuns) {
     177    const bitquad_t * qi = mQuads;
     178
     179    for (unsigned i = 0; i < mRunLength; ++i) {
    155180        assert ((base % QUAD_BITS) == 0);
     181        const auto & r = mRuns[i];
    156182        if (typeOf(r) == Empty) {
    157183            base += lengthOf(r) * QUAD_BITS;
     
    165191        } else { // if (typeOf(r) == Mixed) {
    166192            for (auto l = lengthOf(r); l; --l, ++qi) {
    167                 auto q = *qi;
    168                 assert (q);
     193                auto q = *qi; assert (q);
    169194                const auto c = popcount<bitquad_t>(q);
    170195                if (LLVM_UNLIKELY(remaining < c)) {
     
    192217 * @brief size
    193218 ** ------------------------------------------------------------------------------------------------------------- */
    194 UnicodeSet::size_type UnicodeSet::size() const {
     219UnicodeSet::size_type UnicodeSet::size() const noexcept {
    195220    return std::distance(begin(), end());
    196221}
     
    199224 * @brief count
    200225 ** ------------------------------------------------------------------------------------------------------------- */
    201 UnicodeSet::size_type UnicodeSet::count() const {
     226UnicodeSet::size_type UnicodeSet::count() const noexcept {
    202227    size_type count = 0;
    203     for (const run_t & r : mRuns) {
     228    for (unsigned i = 0; i < mRunLength; ++i) {
     229        const auto & r = mRuns[i];
    204230        if (typeOf(r) == Full) {
     231            assert (lengthOf(r) > 0);
    205232            count += lengthOf(r);
    206233        }
    207234    }
    208235    count *= QUAD_BITS;
    209     for (const bitquad_t q : mQuads) {
    210         count += popcount<bitquad_t>(q);
     236    for (unsigned i = 0; i < mQuadLength; ++i) {
     237        assert (mQuads[i]);
     238        count += popcount<bitquad_t>(mQuads[i]);
    211239    }
    212240    return count;
     
    216244 * @brief front
    217245 ** ------------------------------------------------------------------------------------------------------------- */
    218 UnicodeSet::interval_t UnicodeSet::front() const {
     246interval_t UnicodeSet::front() const noexcept {
    219247    return *begin();
    220248}
     
    223251 * @brief back
    224252 ** ------------------------------------------------------------------------------------------------------------- */
    225 UnicodeSet::interval_t UnicodeSet::back() const {
     253interval_t UnicodeSet::back() const noexcept {
    226254    auto back = begin();
    227255    for (auto i = back; i != end(); back = i++);
     
    232260 * @brief print
    233261 ** ------------------------------------------------------------------------------------------------------------- */
    234 void UnicodeSet::print(llvm::raw_ostream & out) const {
     262void UnicodeSet::print(llvm::raw_ostream & out) const noexcept {
    235263    if (LLVM_UNLIKELY(empty())) {
    236264        out << "()";
     
    252280 * @brief dump
    253281 ** ------------------------------------------------------------------------------------------------------------- */
    254 void UnicodeSet::dump(llvm::raw_ostream & out) const {
    255     auto qi = mQuads.cbegin();
    256     for (const run_t & run : mRuns) {
     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);
    257287        if (typeOf(run) == Empty) {
    258             out << "Empty(" << lengthOf(run) << ")\n";
     288            out << "Empty(" << l << ")\n";
    259289        } else if (typeOf(run) == Full) {
    260             out << "Full(" << lengthOf(run) << ")\n";
     290            out << "Full(" << l << ")\n";
    261291        } else {
    262             for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
    263                 assert (qi != mQuads.cend());
     292            for (const auto qi_end = qi + l; qi != qi_end; ++qi) {
     293                assert (qi != (mQuads + mQuadLength));
    264294                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
    265295            }
     
    271301 * @brief complement
    272302 ** ------------------------------------------------------------------------------------------------------------- */
    273 UnicodeSet UnicodeSet::operator~() const {
    274     std::vector<run_t> runs(mRuns.size());
    275     auto ri = runs.begin();
    276     for (const auto run : mRuns) {
    277         run_type_t type = Empty;
     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;
    278309        if (typeOf(run) == Empty) {           
    279310            type = Full;
    280311        } else if (typeOf(run) == Full) {
    281312            type = Empty;
    282         } else {
    283             type = Mixed;
    284313        }
    285314        *ri++ = { type, lengthOf(run) };
    286315    }
    287     std::vector<bitquad_t> quads(mQuads.size());
    288     auto qi = quads.begin();
    289     for (const auto quad : mQuads) {
    290         *qi++ = ~quad;
    291     }
    292     return UnicodeSet(std::move(runs), std::move(quads), mRuns.get_allocator());
     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);
    293325}
    294326
     
    296328 * @brief intersection
    297329 ** ------------------------------------------------------------------------------------------------------------- */
    298 UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
    299 
    300     std::vector<run_t> runs;
    301     std::vector<bitquad_t> quads;   
    302    
    303     auto i1 = quad_begin(), i2 = other.quad_begin();
    304    
     330UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const noexcept {
     331    RunVector runs;
     332    QuadVector quads;
     333    auto i1 = quad_begin(), i2 = other.quad_begin();   
    305334    for (;;) {
    306335        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
     
    335364    }
    336365    assert (i1 == quad_end() && i2 == other.quad_end());
    337     return UnicodeSet(std::move(runs), std::move(quads), mRuns.get_allocator());
     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);
    338371}
    339372
     
    341374 * @brief union
    342375 ** ------------------------------------------------------------------------------------------------------------- */
    343 UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
    344     std::vector<run_t> runs;
    345     std::vector<bitquad_t> quads;
     376UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const noexcept {
     377    RunVector runs;
     378    QuadVector quads;
    346379    auto i1 = quad_begin(), i2 = other.quad_begin();
    347380    for (;;) {
     
    379412    }
    380413    assert (i1 == quad_end() && i2 == other.quad_end());
    381     return UnicodeSet(std::move(runs), std::move(quads), mRuns.get_allocator());
     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);
    382419}
    383420
     
    385422 * @brief difference
    386423 ** ------------------------------------------------------------------------------------------------------------- */
    387 UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
    388     std::vector<run_t> runs;
    389     std::vector<bitquad_t> quads;
     424UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const noexcept {
     425    RunVector runs;
     426    QuadVector quads;
    390427    auto i1 = quad_begin(), i2 = other.quad_begin();
    391428    for (;;) {
     
    422459    }
    423460    assert (i1 == quad_end() && i2 == other.quad_end());
    424     return UnicodeSet(std::move(runs), std::move(quads), mRuns.get_allocator());
     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);
    425466}
    426467
     
    428469 * @brief symmetric difference
    429470 ** ------------------------------------------------------------------------------------------------------------- */
    430 UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
    431     std::vector<run_t> runs;
    432     std::vector<bitquad_t> quads;
     471UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const noexcept {
     472    RunVector runs;
     473    QuadVector quads;
    433474    auto i1 = quad_begin(), i2 = other.quad_begin();
    434475    for (;;) {
     
    470511    }
    471512    assert (i1 == quad_end() && i2 == other.quad_end());
    472     return UnicodeSet(std::move(runs), std::move(quads), mRuns.get_allocator());
     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);
    473518}
    474519
     
    476521 * @brief equality
    477522 ** ------------------------------------------------------------------------------------------------------------- */
    478 bool UnicodeSet::operator==(const UnicodeSet & other) const {
    479     if (mRuns.size() != other.mRuns.size() || mQuads.size() != other.mQuads.size()) {
     523bool UnicodeSet::operator==(const UnicodeSet & other) const noexcept {
     524    if (LLVM_LIKELY(mRunLength != other.mRunLength || mQuadLength != other.mQuadLength)) {
    480525        return false;
    481526    }
    482     for (auto i = mQuads.begin(), j = other.mQuads.begin(); i != mQuads.end(); ++i, ++j) {
    483         if (*i != *j) return false;
    484     }
    485     for (auto i = mRuns.begin(), j = other.mRuns.begin(); i != mRuns.end(); ++i, ++j) {
    486         if (*i != *j) return false;
     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        }
    487536    }
    488537    return true;
     
    492541 * @brief less operator
    493542 ** ------------------------------------------------------------------------------------------------------------- */
    494 bool UnicodeSet::operator<(const UnicodeSet & other) const {
    495     if (LLVM_LIKELY(mRuns.size() != other.mRuns.size())) {
    496         return mRuns.size() < other.mRuns.size();
    497     } else if (LLVM_LIKELY(mQuads.size() != other.mQuads.size())) {
    498         return (mQuads.size() < other.mQuads.size());
     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);
    499548    } else { // equal run and quad lengths; test their individual values
    500         for (auto ri = mRuns.cbegin(), end = mRuns.cend(), rj = other.mRuns.cbegin(); ri != end; ++ri, ++rj) {
    501             if (*ri < *rj) {
     549        for (unsigned i = 0; i < mRunLength; ++i) {
     550            if (mRuns[i] < other.mRuns[i]) {
    502551                return true;
    503             } else if (*ri > *rj) {
     552            } else if (mRuns[i] > other.mRuns[i]) {
    504553                return false;
    505554            }
    506555        }
    507         for (auto qi = mQuads.cbegin(), end = mQuads.cend(), qj = other.mQuads.cbegin(); qi != end; ++qi, ++qj) {
    508             if (*qi < *qj) {
     556        for (unsigned i = 0; i < mQuadLength; ++i) {
     557            if (mQuads[i] < other.mQuads[i]) {
    509558                return true;
    510             } else if (*qi > *qj) {
     559            } else if (mQuads[i] > other.mQuads[i]) {
    511560                return false;
    512561            }
     
    526575
    527576    codepoint_t offset = cp / QUAD_BITS;
    528     const bitquad_t value = static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK);
    529     auto run = mRuns.begin();
    530     auto quad = mQuads.begin();
    531     length_t l = 0;
    532     run_type_t t = Empty;
     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;
    533584    for (;;) {
    534         std::tie(t, l) = *run;
    535         if (offset < l) {
     585        std::tie(type, length) = mRuns[runIndex];
     586        if (offset < length) {
    536587            break;
    537588        }
    538         if (t == Mixed) {
    539             quad += l;
    540         }
    541         offset -= l;
    542         ++run;
    543     }
    544     if (LLVM_LIKELY(t == Mixed)) {
    545         quad += offset;
    546         *quad |= value;
    547         if (LLVM_LIKELY(*quad != FULL_QUAD_MASK)) {
    548             assert (contains(cp));
    549             return;
    550         }
    551         mQuads.erase(quad);
    552     } else if (t == Empty) {
    553         mQuads.insert(quad, value);
     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;
    554642    } else { // if (t == Full) {
    555643        assert (contains(cp));
    556644        return;
    557645    }
    558     const unsigned remaining = l - (offset + 1);
    559     if (offset == 0) {
    560         *run = std::make_pair(t == Empty ? Mixed : Full, 1);
    561         if (remaining != 0) {
    562             mRuns.insert(++run, std::make_pair(t, remaining));
    563         }
     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;
    564649    } else {
    565         run->second = offset;
    566         if (remaining == 0) {
    567             mRuns.insert(++run, std::make_pair(t == Empty ? Mixed : Full, 1));
     650        const unsigned remaining = length - (offset + 1);
     651        const auto m = (offset && remaining) ? 2 : 1; // splitting the run in the middle?
     652        const auto l = mRunLength + m;
     653        const auto k = runIndex + ((offset != 0) ? 1 : 0);
     654        if (l > mRunCapacity) {
     655            run_t * const newRun = GlobalAllocator.allocate<run_t>(l);
     656            std::memcpy(newRun, mRuns, k * sizeof(run_t));
     657            std::memcpy(newRun + k + m, mRuns + k, (mRunLength - k) * sizeof(run_t));
     658            GlobalAllocator.deallocate<run_t>(mRuns, mRunCapacity);
     659            mRuns = newRun;
     660            mRunCapacity = l;
     661        } else { // reuse the same buffer
     662            std::memmove(mRuns + k + m, mRuns + k, (mRunLength - k) * sizeof(run_t));
     663        }
     664        mRuns[k] = std::make_pair(type == Empty ? Mixed : Full, 1);
     665        if (offset) {
     666            mRuns[k - 1] = std::make_pair(type, offset);
     667        }
     668        if (remaining) {
     669            mRuns[k + 1] = std::make_pair(type, remaining);
     670        }
     671        mRunLength = l;
     672    }
     673    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
     674
     675//    print(llvm::errs());
     676//    llvm::errs() << "\n\n";
     677
     678    assert (contains(cp));
     679}
     680
     681/** ------------------------------------------------------------------------------------------------------------- *
     682 * @brief insert
     683 ** ------------------------------------------------------------------------------------------------------------- */
     684void UnicodeSet::insert(const UnicodeSet & other) noexcept {
     685    RunVector runs;
     686    QuadVector quads;
     687    auto i1 = quad_begin(), i2 = other.quad_begin();
     688    bool changed = false;
     689    for (;;) {
     690        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
     691        const auto n = std::min(i1.length(), i2.length());
     692        if (LLVM_UNLIKELY(n == 0)) {
     693            break;
     694        }
     695        if ((i1.type() == Empty) && (i2.type() == Empty)) {
     696            append_run(Empty, n, runs);
     697            i1 += n;
     698            i2 += n;
     699        } else if ((i1.type() == Full) || (i2.type() == Full)) {
     700            changed |= (i1.type() != Full);
     701            append_run(Full, n, runs);
     702            i1 += n;
     703            i2 += n;
     704        } else if (i1.type() == Empty) {
     705            assert (i2.type() == Mixed);
     706            changed = true;
     707            for (unsigned i = 0; i != n; ++i, ++i2) {
     708                append_quad(i2.quad(), quads, runs);
     709            }
     710            i1 += n;
     711        } else if (i2.type() == Empty) {
     712            assert (i1.type() == Mixed);
     713            for (unsigned i = 0; i != n; ++i, ++i1) {
     714                append_quad(i1.quad(), quads, runs);
     715            }
     716            i2 += n;
     717        } else { // both Mixed
     718            assert (i1.type() == Mixed && i2.type() == Mixed);
     719            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
     720                changed |= (i2.quad() &~ i1.quad());
     721                append_quad(i1.quad() | i2.quad(), quads, runs);
     722            }
     723        }
     724    }
     725    assert (i1 == quad_end() && i2 == other.quad_end());
     726    if (LLVM_LIKELY(changed)) {
     727        assign(this, runs, quads);
     728    }
     729}
     730
     731/** ------------------------------------------------------------------------------------------------------------- *
     732 * @brief invert
     733 ** ------------------------------------------------------------------------------------------------------------- */
     734void UnicodeSet::invert() noexcept {
     735
     736    if (LLVM_UNLIKELY(mRunCapacity == 0)) {
     737        run_t * const runs = GlobalAllocator.allocate<run_t>(mRunLength);
     738        for (unsigned i = 0; i < mRunLength; ++i) {
     739            auto & run = mRuns[i];
     740            const auto l = lengthOf(run);
     741            if (typeOf(run) == Empty) {
     742                runs[i] = std::make_pair(Full, l);
     743            } else if (typeOf(run) == Full) {
     744                runs[i] = std::make_pair(Empty, l);
     745            } else {
     746                runs[i] = std::make_pair(Mixed, l);
     747            }
     748        }
     749        mRuns = runs;
     750        mRunCapacity = mRunLength;
     751    } else {
     752        for (unsigned i = 0; i < mRunLength; ++i) {
     753            auto & run = mRuns[i];
     754            if (typeOf(run) == Empty) {
     755                std::get<0>(run) = Full;
     756            } else if (typeOf(run) == Full) {
     757                std::get<0>(run) = Empty;
     758            }
     759        }
     760    }
     761
     762    if (mQuadLength) {
     763        if (mQuadCapacity == 0) {
     764            bitquad_t * const quads = GlobalAllocator.allocate<bitquad_t>(mQuadLength);
     765            for (unsigned i = 0; i != mQuadLength; ++i) {
     766                quads[i] = ~mQuads[i];
     767            }
     768            mQuads = quads;
     769            mQuadCapacity = mQuadLength;
    568770        } else {
    569             mRuns.insert(++run, {std::make_pair(t == Empty ? Mixed : Full, 1), std::make_pair(t, remaining)});
    570         }
    571     }
    572 
    573     assert (verify(mRuns, mQuads));
    574     assert (contains(cp));
     771            for (unsigned i = 0; i != mQuadLength; ++i) {
     772                mQuads[i] = ~mQuads[i];
     773            }
     774        }
     775    }
     776
    575777}
    576778
     
    578780 * @brief insert_range
    579781 ** ------------------------------------------------------------------------------------------------------------- */
    580 void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi)  {
     782void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi) {
    581783
    582784    if (LLVM_UNLIKELY(lo > hi)) {
     
    587789
    588790    // Create a temporary run and quad set for the given range
    589     std::vector<run_t> runs;
    590     std::vector<bitquad_t> quads;
     791    RunVector runs;
     792    QuadVector quads;
    591793
    592794    codepoint_t lo_index = lo / QUAD_BITS;
    593795    codepoint_t hi_index = hi / QUAD_BITS;
    594796
    595     auto ri = mRuns.cbegin();
    596     auto qi = mQuads.cbegin();
     797    const run_t * ri = mRuns;
     798    const run_t * const ri_end = mRuns + mRunLength;
     799
     800    const bitquad_t * qi = mQuads;
     801    const bitquad_t * const qi_end = mQuads + mQuadLength;
    597802
    598803    codepoint_t length = 0;
     
    601806    // Advance past any runs prior to the lo_index
    602807    for (;;) {
    603         assert (ri != mRuns.cend());
    604         std::tie(type, length) = *ri;       
     808        assert (ri < ri_end);
     809        std::tie(type, length) = *ri;
    605810        if (lo_index < length) {
    606811            break;
    607812        }
    608813        if (type == Mixed) {
    609             assert (std::distance(qi, mQuads.cend()) >= length);
     814            assert ((qi + length) <= qi_end);
    610815            qi += length;
    611816        }
     
    615820    }
    616821
    617     // Now record the runs and any quads prior to lo_index
    618     runs.assign(mRuns.cbegin(), ri++);
     822    // Now record the runs and any quads prior to lo_index   
     823    runs.append<const run_t *>(mRuns, ri++);
    619824    if (lo_index) {
    620825        runs.emplace_back(type, lo_index);
    621826        if (type == Mixed) {
    622             assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) >= lo_index);
     827            assert ((qi + lo_index) <= qi_end);
    623828            qi += lo_index;
    624829        }
    625830        hi_index -= lo_index;
     831        assert (length >= lo_index);
    626832        length -= lo_index;
    627833    }
    628834
    629     quads.assign(mQuads.cbegin(), qi);
     835    quads.append<const bitquad_t *>(mQuads, qi);
    630836    // We now have everything up to the first quad added to our temporary buffers; merge in the first new quad.
    631     bitquad_t lo_quad = (FULL_QUAD_MASK << (lo & MOD_QUAD_BIT_MASK));
    632     bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - (hi & MOD_QUAD_BIT_MASK)));
     837    bitquad_t lo_quad = (FULL_QUAD_MASK << (lo & QUAD_LIMIT));
     838    bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - (hi & QUAD_LIMIT)));
    633839
    634840    // If our original quad is full, just append a Full run
     
    638844        if (hi_index == 0) {
    639845            lo_quad &= hi_quad;
    640         }
     846        }       
    641847        if (type == Mixed) {
    642             assert (std::distance(qi, mQuads.cend()) > 0);
     848            assert (qi < qi_end);
    643849            lo_quad |= *qi++;
    644850        }
    645851        append_quad(lo_quad, quads, runs);
    646852    }
     853
     854    assert (length > 0);
    647855    --length;
    648856
     
    653861        append_run(Full, hi_index - 1, runs);
    654862        // Advance past original quads that were filled in
    655         while (ri != mRuns.cend()) {
     863        while (length < hi_index) {
    656864            if (type == Mixed) {
    657                 assert (std::distance(qi, mQuads.cend()) >= length);
     865                assert ((qi + length) <= qi_end);
    658866                qi += length;
    659867            }
     868            hi_index -= length;
     869            assert (ri < ri_end);
    660870            std::tie(type, length) = *ri++;
    661             if (hi_index < length) {
    662                 break;
    663             }
    664             hi_index -= length;
    665             length = 0;
    666         }       
     871        }
     872        length -= hi_index;
    667873        // Write out the hi_quad value
    668874        if (LLVM_UNLIKELY(type == Full)) {
     
    670876        } else {
    671877            if (type == Mixed) {
    672                 assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) > hi_index);
     878                assert ((qi + hi_index) < qi_end);
    673879                qi += hi_index;
    674880                hi_quad |= *qi++;
     
    677883        }
    678884    }
    679 
    680     // And append any remaining values from the original data
    681     assert (length >= hi_index);
    682     append_run(type, length - hi_index, runs);
    683     assert ("We wrote all the runs but still have remaining quads?" && (ri != mRuns.cend() || qi == mQuads.cend()));
    684     runs.insert(runs.end(), ri, mRuns.cend());
    685     quads.insert(quads.end(), qi, mQuads.cend());
    686     assert (verify(runs, quads));
    687     mRuns.assign(runs.cbegin(), runs.cend());
    688     mQuads.assign(quads.cbegin(), quads.cend());   
     885    assert ("We wrote all the runs but still have remaining quads?" && (ri != ri_end || qi == qi_end));
     886    append_run(type, length, runs);
     887
     888    // append any remaining values from the original data
     889    runs.append<const run_t *>(ri, ri_end);
     890    quads.append<const bitquad_t *>(qi, qi_end);
     891    assign(this, runs, quads);
    689892}
    690893
     
    695898 * Return whether this UnicodeSet contains the specified code point
    696899 ** ------------------------------------------------------------------------------------------------------------- */
    697 bool UnicodeSet::contains(const codepoint_t cp) const {
     900bool UnicodeSet::contains(const codepoint_t cp) const noexcept {
    698901    codepoint_t offset = cp / QUAD_BITS;
    699     auto quad = mQuads.cbegin();
    700     for (const auto r : mRuns) {
    701         length_t l = 0;
    702         run_type_t t = Empty;
    703         std::tie(t, l) = r;
    704         if (offset < l) {
    705             if (t == Mixed) {
    706                 quad += offset;
    707                 return (*quad & static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK)) != 0;
    708             }
    709             return (t == Full);
    710         }
    711         if (t == Mixed) {
    712             quad += l;
     902    for (unsigned runIndex = 0, quadIndex = 0; runIndex < mRunLength; ++runIndex) {
     903        length_t length = 0;
     904        run_type_t type = Empty;
     905        std::tie(type, length) = mRuns[runIndex];
     906        if (offset < length) {
     907            if (type == Mixed) {
     908                return (mQuads[quadIndex + offset] & (static_cast<bitquad_t>(1) << (cp & QUAD_LIMIT))) != 0;
     909            }
     910            return (type == Full);
     911        }
     912        if (type == Mixed) {
     913            quadIndex += length;
    713914        }       
    714         offset -= l;
     915        offset -= length;
    715916    }
    716917    return false;
     
    722923 * @param hi_codepoint
    723924 *
    724  * Return true if this UnicodeSet contains any code point(s) between lo and hi (inclusive)
    725  ** ------------------------------------------------------------------------------------------------------------- */
    726 bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const {
     925 * Return true if this UnicodeSet contains any code point between lo and hi (inclusive)
     926 ** ------------------------------------------------------------------------------------------------------------- */
     927bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const noexcept {
    727928    for (auto range : *this) {
    728929        if (range.second < lo) {
     
    743944 * Return true if this UnicodeSet has a non-empty intersection with other
    744945 ** ------------------------------------------------------------------------------------------------------------- */
    745 bool UnicodeSet::intersects(const UnicodeSet & other) const {
     946bool UnicodeSet::intersects(const UnicodeSet & other) const noexcept {
    746947    for (auto i1 = quad_begin(), i2 = other.quad_begin();; ) {
    747948        auto n = std::min(i1.length(), i2.length());
     
    770971 * Return true if this UnicodeSet is a subset of other
    771972 ** ------------------------------------------------------------------------------------------------------------- */
    772 bool UnicodeSet::subset(const UnicodeSet & other) const {
     973bool UnicodeSet::subset(const UnicodeSet & other) const noexcept {
    773974    for (auto i1 = quad_begin(), i2 = other.quad_begin();; ) {
    774975        auto n = std::min(i1.length(), i2.length());
     
    8961097        } else { // if (typeOf(t) == Mixed)
    8971098            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
    898                 const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
    899 
     1099                const bitquad_t m = ((~*mQuadIterator)) & (FULL_QUAD_MASK << mQuadOffset);
    9001100                // If we found a marker in m, it marks the end of our current interval.
    9011101                // Find it and break out of the loop.
     
    9251125    assert (mMinCodePoint <= mMaxCodePoint);
    9261126}
    927    
     1127
    9281128/** ------------------------------------------------------------------------------------------------------------- *
    9291129 * @brief Empty/Full Set Constructor
    9301130 ** ------------------------------------------------------------------------------------------------------------- */
    931 UnicodeSet::UnicodeSet(run_type_t emptyOrFull, ProxyAllocator<> allocator)
    932 : mRuns(allocator)
    933 , mQuads(allocator) {
    934     assert((emptyOrFull == Empty) || (emptyOrFull == Full));
    935     append_run(emptyOrFull, UNICODE_QUAD_COUNT, mRuns);
    936     assert (verify(mRuns, mQuads));
     1131UnicodeSet::UnicodeSet() noexcept
     1132: mRuns(GlobalAllocator.allocate<run_t>(1))
     1133, mQuads(nullptr)
     1134, mRunLength(1)
     1135, mQuadLength(0)
     1136, mRunCapacity(1)
     1137, mQuadCapacity(0) {
     1138    mRuns[0] = std::make_pair(Empty, UNICODE_QUAD_COUNT);
     1139    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
    9371140}
    9381141           
     
    9401143 * @brief Singleton Set Constructor
    9411144 ** ------------------------------------------------------------------------------------------------------------- */
    942 UnicodeSet::UnicodeSet(const codepoint_t codepoint, ProxyAllocator<> allocator)
    943 : mRuns(allocator)
    944 , mQuads(allocator) {
    945     const codepoint_t quad_no = codepoint / QUAD_BITS;
    946     append_run(Empty, quad_no, mRuns);
    947     append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
    948     append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
    949     assert (verify(mRuns, mQuads));
     1145UnicodeSet::UnicodeSet(const codepoint_t codepoint) noexcept
     1146: mRuns(GlobalAllocator.allocate<run_t>(3))
     1147, mQuads(GlobalAllocator.allocate<bitquad_t>(1))
     1148, mRunLength(0)
     1149, mQuadLength(1)
     1150, mRunCapacity(3)
     1151, mQuadCapacity(1) {
     1152    assert (codepoint <= UNICODE_MAX);
     1153    const codepoint_t offset = codepoint / QUAD_BITS;
     1154    const codepoint_t remaining = UNICODE_QUAD_COUNT - (offset + 1);   
     1155    unsigned l = 0;
     1156    if (offset) {
     1157        mRuns[l++] = std::make_pair(Empty, offset);
     1158    }
     1159    mRuns[l++] = std::make_pair(Mixed, 1);
     1160    if (remaining) {
     1161        mRuns[l++] = std::make_pair(Empty, remaining);
     1162    }
     1163    mRunLength = l;
     1164    mQuads[0] = static_cast<bitquad_t>(1) << (codepoint & QUAD_LIMIT);
     1165    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
     1166    assert (contains(codepoint));
     1167    assert (codepoint == 0 || !contains(codepoint - 1));
     1168    assert (codepoint == UNICODE_MAX || !contains(codepoint + 1));
    9501169}
    9511170
     
    9531172 * @brief Range Set Constructor
    9541173 ** ------------------------------------------------------------------------------------------------------------- */
    955 UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi, ProxyAllocator<> allocator)
    956 : mRuns(allocator)
    957 , mQuads(allocator)
    958 {
     1174UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi) noexcept
     1175: mRuns(GlobalAllocator.allocate<run_t>(5))
     1176, mQuads(GlobalAllocator.allocate<bitquad_t>(2))
     1177, mRunLength(0)
     1178, mQuadLength(0)
     1179, mRunCapacity(5)
     1180, mQuadCapacity(2) {
     1181
    9591182    const codepoint_t lo_index = lo / QUAD_BITS;
    9601183    const codepoint_t hi_index = hi / QUAD_BITS;
    961     const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
    962     const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
    963     const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
    964     const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
    965     append_run(Empty, lo_index, mRuns);
    966     bitquad_t mask = hi_quad;
     1184    const codepoint_t lo_offset = lo & QUAD_LIMIT;
     1185    const codepoint_t hi_offset = hi & QUAD_LIMIT;
     1186
     1187    assert (lo <= hi);
     1188    assert (hi <= UNICODE_MAX);
     1189
     1190    // Assuming that Empty and Full quads can be of 0 length and Mixed are
     1191    // length 1, we have the following cases:
     1192
     1193    // LO_INDEX == HI_INDEX && LO_OFFSET == 0 && HI_OFFSET == QUAD_BITS
     1194
     1195    //             Empty           Full            Empty
     1196    //      |                 |############|                 |
     1197
     1198    // LO_INDEX == HI_INDEX && (LO_OFFSET != 0 || HI_OFFSET != QUAD_BITS)
     1199
     1200    //             Empty          Mixed             Empty
     1201    //      |                 |  #######   |                 |
     1202
     1203    // LO_INDEX != HI_INDEX && LO_OFFSET != 0 && HI_OFFSET == QUAD_BITS
     1204
     1205    //          Empty    Mixed     Full            Empty
     1206    //      |           |  ###|############|                 |
     1207
     1208    // LO_INDEX != HI_INDEX && LO_OFFSET == 0 && HI_OFFSET != QUAD_BITS
     1209
     1210    //             Empty           Full     Mixed    Empty
     1211    //      |                 |############|###  |           |
     1212
     1213    // LO_INDEX != HI_INDEX && LO_OFFSET != 0 && HI_OFFSET != QUAD_BITS
     1214
     1215    //          Empty    Mixed     Full     Mixed    Empty
     1216    //      |           |  ###|############|###  |           |
     1217
     1218    if (LLVM_LIKELY(lo_index != 0)) {
     1219        mRuns[0] = std::make_pair(Empty, lo_index);
     1220        mRunLength = 1;
     1221    }
    9671222    if (lo_index == hi_index) {
    968         mask &= lo_quad;
     1223        if ((lo_offset == 0) && (hi_offset == QUAD_LIMIT)) {
     1224            mRuns[mRunLength++] = std::make_pair(Full, 1);
     1225        } else {
     1226            mRuns[mRunLength++] = std::make_pair(Mixed, 1);
     1227            const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
     1228            const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - hi_offset));
     1229            mQuads[0] = lo_quad & hi_quad;
     1230            mQuadLength = 1;
     1231        }
     1232
    9691233    } else {
    970         append_quad(lo_quad, mQuads, mRuns);
    971         append_run(Full, hi_index - (lo_index + 1), mRuns);
    972     }
    973     append_quad(mask, mQuads, mRuns);
    974     append_run(Empty, UNICODE_QUAD_COUNT - (hi_index + 1), mRuns);
    975     assert (verify(mRuns, mQuads));
     1234        const auto lm = ((lo_offset != 0) ? 1U : 0U);
     1235        const auto rm = ((hi_offset != QUAD_LIMIT) ? 1U : 0U);
     1236        const auto d = (hi_index - lo_index) - (lm + rm) + 1;
     1237        if (lo_offset != 0) {
     1238            mRuns[mRunLength++] = std::make_pair(Mixed, 1);
     1239            mQuads[0] = (FULL_QUAD_MASK << lo_offset);
     1240            mQuadLength = 1;
     1241        }
     1242        if (d != 0) {
     1243            mRuns[mRunLength++] = std::make_pair(Full, d);
     1244        }
     1245        if (hi_offset != QUAD_LIMIT) {
     1246            mRuns[mRunLength++] = std::make_pair(Mixed, 1);
     1247            const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - hi_offset));
     1248            mQuads[mQuadLength++] = hi_quad;
     1249        }
     1250    }
     1251    const auto remaining = UNICODE_QUAD_COUNT - (hi_index + 1);
     1252    if (LLVM_LIKELY(remaining != 0)) {
     1253        mRuns[mRunLength++] = std::make_pair(Empty, remaining);
     1254    }
     1255    assert (mRunLength <= mRunCapacity);
     1256    assert (mQuadLength <= mQuadCapacity);
     1257    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
     1258    assert (contains(lo) && contains(hi));
     1259    assert (lo == 0 || !contains(lo - 1));
     1260    assert (hi == UNICODE_MAX || !contains(hi + 1));
    9761261}
    9771262
     
    9791264 * @brief Range List Set Constructor
    9801265 ** ------------------------------------------------------------------------------------------------------------- */
    981 template <typename itr>
    982 void convertIntervalRangesToSparseSet(const itr begin, const itr end, UnicodeSet::RunVector & mRuns, UnicodeSet::QuadVector & mQuads) {
    983 
    984     std::vector<run_t> runs;
    985     std::vector<bitquad_t> quads;
     1266template <typename iterator>
     1267inline void convertIntervalsToUnicodeSet(const iterator begin, const iterator end, RunVector & runs, QuadVector & quads) noexcept {
    9861268
    9871269    assert ("interval list must be totally ordered" && std::is_sorted(begin, end, [](const interval_t l, const interval_t r) {
     
    10001282        const codepoint_t lo_index = (lo / QUAD_BITS);
    10011283        const codepoint_t hi_index = (hi / QUAD_BITS);
    1002         const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
    1003         const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
     1284        const codepoint_t lo_offset = lo & QUAD_LIMIT;
     1285        const codepoint_t hi_offset = hi & QUAD_LIMIT;
    10041286        const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
    1005         const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
     1287        const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_LIMIT - hi_offset));
    10061288        append_run(Empty, lo_index - prior_index, runs);
    10071289        if (lo_index == hi_index) {
     
    10261308    if (prior_index < UNICODE_QUAD_COUNT) {
    10271309        append_run(Empty, UNICODE_QUAD_COUNT - prior_index, runs);
    1028     }   
    1029     mRuns.assign(runs.begin(), runs.end());
    1030     mQuads.assign(quads.begin(), quads.end());
     1310    }
    10311311}
    10321312
     
    10341314 * @brief Interval Range Constructor
    10351315 ** ------------------------------------------------------------------------------------------------------------- */
    1036 UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end, ProxyAllocator<> allocator)
    1037 : mRuns(allocator)
    1038 , mQuads(allocator) {
    1039     convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
    1040     assert (verify(mRuns, mQuads));
     1316UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end) noexcept
     1317: mRuns(nullptr)
     1318, mQuads(nullptr)
     1319, mRunLength(0)
     1320, mQuadLength(0)
     1321, mRunCapacity(0)
     1322, mQuadCapacity(0) {
     1323    RunVector runs;
     1324    QuadVector quads;
     1325
     1326    convertIntervalsToUnicodeSet(begin, end, runs, quads);
     1327
     1328    const auto n = runs.size();
     1329    assert (n > 0 && n < UNICODE_QUAD_COUNT);
     1330    mRuns = GlobalAllocator.allocate<run_t>(n);
     1331    mRunCapacity = n;
     1332    mRunLength = n;
     1333    std::memcpy(mRuns, runs.data(), n * sizeof(run_t));
     1334
     1335    const auto m = quads.size();
     1336    assert (m < UNICODE_QUAD_COUNT);
     1337    if (m) {
     1338        mQuads = GlobalAllocator.allocate<bitquad_t>(m);
     1339        mQuadCapacity = m;
     1340        mQuadLength = m;
     1341        std::memcpy(mQuads, quads.data(), m * sizeof(bitquad_t));
     1342    }
     1343
     1344    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
    10411345}
    10421346
     
    10441348 * @brief Interval Range Constructor
    10451349 ** ------------------------------------------------------------------------------------------------------------- */
    1046 UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end, ProxyAllocator<> allocator)
    1047 : mRuns(allocator)
    1048 , mQuads(allocator) {
    1049     convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
    1050     assert (verify(mRuns, mQuads));
     1350UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end) noexcept
     1351: mRuns(nullptr)
     1352, mQuads(nullptr)
     1353, mRunLength(0)
     1354, mQuadLength(0)
     1355, mRunCapacity(0)
     1356, mQuadCapacity(0) {
     1357    RunVector runs;
     1358    QuadVector quads;
     1359
     1360    convertIntervalsToUnicodeSet(begin, end, runs, quads);
     1361
     1362    const auto n = runs.size();
     1363    assert (n > 0 && n < UNICODE_QUAD_COUNT);
     1364    mRuns = GlobalAllocator.allocate<run_t>(n);
     1365    mRunCapacity = n;
     1366    mRunLength = n;
     1367    std::memcpy(mRuns, runs.data(), n * sizeof(run_t));
     1368
     1369    const auto m = quads.size();
     1370    assert (m < UNICODE_QUAD_COUNT);
     1371    if (m) {
     1372        mQuads = GlobalAllocator.allocate<bitquad_t>(m);
     1373        mQuadCapacity = m;
     1374        mQuadLength = m;
     1375        std::memcpy(mQuads, quads.data(), m * sizeof(bitquad_t));
     1376    }
     1377
     1378    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
     1379}
     1380
     1381/** ------------------------------------------------------------------------------------------------------------- *
     1382 * @brief Move Constructor
     1383 ** ------------------------------------------------------------------------------------------------------------- */
     1384UnicodeSet::UnicodeSet(const UnicodeSet && other) noexcept
     1385: mRuns(other.mRuns)
     1386, mQuads(other.mQuads)
     1387, mRunLength(other.mRunLength)
     1388, mQuadLength(other.mQuadLength)
     1389, mRunCapacity(other.mRunLength)
     1390, mQuadCapacity(other.mQuadLength) {
     1391    assert (verify(mRuns, other.mRunLength, mQuads, other.mQuadLength));
     1392}
     1393
     1394/** ------------------------------------------------------------------------------------------------------------- *
     1395 * @brief Move Assignment Constructor
     1396 ** ------------------------------------------------------------------------------------------------------------- */
     1397UnicodeSet & UnicodeSet::operator=(const UnicodeSet && other) noexcept {
     1398    if (mRunCapacity) {
     1399        GlobalAllocator.deallocate<run_t>(mRuns, mRunCapacity);
     1400    }
     1401    if (mQuadCapacity) {
     1402        GlobalAllocator.deallocate<bitquad_t>(mQuads, mQuadCapacity);
     1403    }
     1404    mRuns = other.mRuns;
     1405    mQuads = other.mQuads;
     1406    mRunLength = other.mRunLength;
     1407    mQuadLength = other.mQuadLength;
     1408    mRunCapacity = other.mRunCapacity;
     1409    mQuadCapacity = other.mQuadCapacity;
     1410    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
     1411    return *this;
    10511412}
    10521413
     
    10541415 * @brief Copy Constructor
    10551416 ** ------------------------------------------------------------------------------------------------------------- */
    1056 UnicodeSet::UnicodeSet(const UnicodeSet & other, ProxyAllocator<> allocator)
    1057 : mRuns(other.mRuns, allocator)
    1058 , mQuads(other.mQuads, allocator) {
    1059     assert (verify(mRuns, mQuads));
    1060 }
    1061 
    1062 /** ------------------------------------------------------------------------------------------------------------- *
    1063  * @brief Initializer Constructor
    1064  ** ------------------------------------------------------------------------------------------------------------- */
    1065 UnicodeSet::UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q, ProxyAllocator<> allocator)
    1066 : mRuns(r.begin(), r.end(), allocator)
    1067 , mQuads(q.begin(), q.end(), allocator) {
    1068     assert (verify(mRuns, mQuads));
    1069 }
    1070 
    1071 /** ------------------------------------------------------------------------------------------------------------- *
    1072  * @brief Internal Vector Constructor
    1073  ** ------------------------------------------------------------------------------------------------------------- */
    1074 inline UnicodeSet::UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q, ProxyAllocator<> allocator)
    1075 : mRuns(r.begin(), r.end(), allocator)
    1076 , mQuads(q.begin(), q.end(), allocator) {
    1077     assert (verify(mRuns, mQuads));
    1078 }
    1079 
    1080 }
    1081 
     1417UnicodeSet::UnicodeSet(const UnicodeSet & other) noexcept
     1418: mRuns(other.mRuns)
     1419, mQuads(other.mQuads)
     1420, mRunLength(other.mRunLength)
     1421, mQuadLength(other.mQuadLength)
     1422, mRunCapacity(0) // lazily ensure reallocation on modification
     1423, mQuadCapacity(0) {
     1424    assert (verify(mRuns, other.mRunLength, mQuads, other.mQuadLength));
     1425}
     1426
     1427/** ------------------------------------------------------------------------------------------------------------- *
     1428 * @brief Copy Assignment Constructor
     1429 ** ------------------------------------------------------------------------------------------------------------- */
     1430UnicodeSet & UnicodeSet::operator=(const UnicodeSet & other) noexcept {
     1431    if (mRunCapacity) {
     1432        GlobalAllocator.deallocate<run_t>(mRuns, mRunCapacity);
     1433    }
     1434    if (mQuadCapacity) {
     1435        GlobalAllocator.deallocate<bitquad_t>(mQuads, mQuadCapacity);
     1436    }
     1437    mRuns = other.mRuns;
     1438    mQuads = other.mQuads;
     1439    mRunLength = other.mRunLength;
     1440    mQuadLength = other.mQuadLength;
     1441    mRunCapacity = 0; // lazily ensure reallocation on modification
     1442    mQuadCapacity = 0;
     1443    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
     1444    return *this;
     1445}
     1446
     1447/** ------------------------------------------------------------------------------------------------------------- *
     1448 * @brief Internal / Predefined Constructor
     1449 ** ------------------------------------------------------------------------------------------------------------- */
     1450UnicodeSet::UnicodeSet(run_t * const runs, const uint32_t runLength, const uint32_t runCapacity,
     1451                       bitquad_t * const quads, const uint32_t quadLength, const uint32_t quadCapacity) noexcept
     1452: mRuns(runs)
     1453, mQuads(quads)
     1454, mRunLength(runLength)
     1455, mQuadLength(quadLength)
     1456, mRunCapacity(runCapacity)
     1457, mQuadCapacity(quadCapacity) {
     1458    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
     1459}
     1460
     1461/** ------------------------------------------------------------------------------------------------------------- *
     1462 * @brief Deprecated Constructor
     1463 ** ------------------------------------------------------------------------------------------------------------- */
     1464UnicodeSet::UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q) noexcept
     1465: mRuns(GlobalAllocator.allocate<run_t>(r.size()))
     1466, mQuads(q.size() == 0 ? nullptr : GlobalAllocator.allocate<bitquad_t>(q.size()))
     1467, mRunLength(r.size())
     1468, mQuadLength(q.size())
     1469, mRunCapacity(r.size())
     1470, mQuadCapacity(q.size()) {
     1471    std::copy(r.begin(), r.end(), mRuns);
     1472    std::copy(q.begin(), q.end(), mQuads);
     1473    assert (verify(mRuns, mRunLength, mQuads, mQuadLength));
     1474}
     1475
     1476}
Note: See TracChangeset for help on using the changeset viewer.