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

Last change on this file since 5240 was 5240, checked in by nmedfort, 2 years ago

Cleaned up memory leaks + some warning messages.

File size: 35.6 KB
Line 
1//
2// unicode_set.cpp - representing and manipulating sets of Unicode
3// characters, based on data from UCD - the Unicode Character Database
4//
5// Robert D. Cameron
6// September 18, 2014
7//
8// Licensed under Open Software License 3.0.
9//
10// Unicode Sparse Bitset Representation
11//
12// The Unicode Sparse Bitset representation is based on
13// (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
14// (b) Specifying the quads using a run-length encoding, in which each run
15//     is Empty (quads contain no members), Mixed (quads contain some members and
16//     some nonmembers) or Full (all codepoints in each quad are members of the set).
17// (c) Explicitly listing all the quads of Mixed type.
18//
19
20#include "unicode_set.h"
21#include "assert.h"
22#include <string>
23#include <llvm/Support/raw_ostream.h>
24#include <llvm/Support/Format.h>
25#include <array>
26
27namespace UCD {
28
29using bitquad_t = UnicodeSet::bitquad_t;
30using run_t = UnicodeSet::run_t;
31using interval_t = UnicodeSet::interval_t;
32using codepoint_t = UnicodeSet::codepoint_t;
33
34//
35// Select the correct built-in scan function, dependent on whatever
36// bitquad_t resolves to, when scan_forwrad_zeroes<bitquad_t> is called.
37template <typename T> int scan_forward_zeroes(T x);
38template <> inline int scan_forward_zeroes<unsigned int>(unsigned int x){return __builtin_ctz(x);}
39template <> inline int scan_forward_zeroes<unsigned long>(unsigned long x){return __builtin_ctzl(x);}
40template <> inline int scan_forward_zeroes<unsigned long long>(unsigned long long x){return __builtin_ctzll(x);}
41
42SlabAllocator<> UnicodeSet::mAllocator;
43
44const uint64_t QUAD_BITS = (8 * sizeof(bitquad_t));
45const uint64_t MOD_QUAD_BIT_MASK = QUAD_BITS - 1;
46const uint64_t UNICODE_QUAD_COUNT = (UNICODE_MAX + 1) / QUAD_BITS;
47const bitquad_t FULL_QUAD_MASK = -1;
48
49inline run_type_t typeOf(const run_t & run) {
50    return run.first;
51}
52
53inline UnicodeSet::length_t lengthOf(const run_t & run) {
54    return run.second;
55}
56
57/** ------------------------------------------------------------------------------------------------------------- *
58 * @brief append_run
59 ** ------------------------------------------------------------------------------------------------------------- */
60template <class RunVector>
61inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) {
62    if (LLVM_UNLIKELY(length == 0)) {
63        return;
64    } else if (!runs.empty() && typeOf(runs.back()) == type) {
65        std::get<1>(runs.back()) += length;
66        return;
67    }
68    runs.emplace_back(type, length);
69}
70
71/** ------------------------------------------------------------------------------------------------------------- *
72 * @brief append_quad
73 ** ------------------------------------------------------------------------------------------------------------- */
74template <class QuadVector, class RunVector>
75inline void append_quad(const bitquad_t quad, QuadVector & quads, RunVector & runs) {
76    run_type_t type = Empty;
77    if (LLVM_UNLIKELY(quad == 0)) {
78        type = Empty;
79    } else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
80        type = Full;
81    } else {
82        quads.emplace_back(quad);
83        type = Mixed;
84    }
85    append_run(type, 1, runs);
86}
87
88#ifndef NDEBUG
89/** ------------------------------------------------------------------------------------------------------------- *
90 * @brief verify
91 *
92 * Sanity check for each function that constructs or modifies a UnicodeSet
93 ** ------------------------------------------------------------------------------------------------------------- */
94template <class RunVector, class QuadVector>
95inline bool verify(const RunVector & runs, const QuadVector & quads) {
96    unsigned sum = 0;
97    unsigned mixedQuads = 0;
98    for (auto run : runs) {
99        const auto l = lengthOf(run);
100        if (l == 0) {
101            throw std::runtime_error("Zero-length quad found!");
102        }
103        if (typeOf(run) == Mixed) {
104            mixedQuads += l;
105        }
106        sum += l;
107    }
108    if (sum != UNICODE_QUAD_COUNT) {
109        throw std::runtime_error("Invalid quad count: found " + std::to_string(sum) + " but expected " + std::to_string(UNICODE_QUAD_COUNT));
110    }
111    if (mixedQuads != quads.size()) {
112        throw std::runtime_error("Invalid mixed quad count: found " + std::to_string(quads.size()) + " but expected " + std::to_string(mixedQuads));
113    }
114    for (auto quad : quads) {
115        if (quad == 0) {
116            throw std::runtime_error("Empty quad found in Mixed quad array!");
117        } else if (quad == FULL_QUAD_MASK) {
118            throw std::runtime_error("Full quad found in Mixed quad array!");
119        }
120    }
121    return true;
122}
123#endif
124
125/** ------------------------------------------------------------------------------------------------------------- *
126 * @brief empty
127 ** ------------------------------------------------------------------------------------------------------------- */
128bool UnicodeSet::empty() const {
129    return (mRuns.size() == 1) && typeOf(mRuns.front()) == Empty;
130}
131
132/** ------------------------------------------------------------------------------------------------------------- *
133 * @brief size
134 ** ------------------------------------------------------------------------------------------------------------- */
135UnicodeSet::size_type UnicodeSet::size() const {
136    return std::distance(begin(), end());
137}
138
139/** ------------------------------------------------------------------------------------------------------------- *
140 * @brief front
141 ** ------------------------------------------------------------------------------------------------------------- */
142UnicodeSet::interval_t UnicodeSet::front() const {
143    return *begin();
144}
145
146/** ------------------------------------------------------------------------------------------------------------- *
147 * @brief back
148 ** ------------------------------------------------------------------------------------------------------------- */
149UnicodeSet::interval_t UnicodeSet::back() const {
150    auto back = begin();
151    for (auto i = back; i != end(); back = i++);
152    return *back;
153}
154
155/** ------------------------------------------------------------------------------------------------------------- *
156 * @brief dump
157 ** ------------------------------------------------------------------------------------------------------------- */
158void UnicodeSet::dump(llvm::raw_ostream & out) const {
159    auto qi = mQuads.cbegin();
160    for (const run_t & run : mRuns) {
161        if (typeOf(run) == Empty) {
162            out << "Empty(" << lengthOf(run) << ")\n";
163        }
164        else if (typeOf(run) == Full) {
165            out << "Full(" << lengthOf(run) << ")\n";
166        }
167        else {
168            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
169                assert (qi != mQuads.cend());
170                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
171            }
172        }
173    }
174}
175
176/** ------------------------------------------------------------------------------------------------------------- *
177 * @brief complement
178 ** ------------------------------------------------------------------------------------------------------------- */
179UnicodeSet UnicodeSet::operator~() const {
180    std::vector<run_t> runs;
181    std::vector<bitquad_t> quads;
182    runs.reserve(mRuns.size());
183    quads.reserve(mQuads.size());
184    auto qi = quads.cbegin();
185    for (const run_t & run : mRuns) {
186        if (typeOf(run) == Empty) {
187            append_run(Full, lengthOf(run), runs);
188        }
189        else if (typeOf(run) == Full) {
190            append_run(Empty, lengthOf(run), runs);
191        }
192        else {
193            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
194                assert (qi != quads.cend());
195                append_quad(FULL_QUAD_MASK ^ *qi, quads, runs);
196            }
197        }
198    }
199    return UnicodeSet(std::move(runs), std::move(quads));
200}
201
202/** ------------------------------------------------------------------------------------------------------------- *
203 * @brief intersection
204 ** ------------------------------------------------------------------------------------------------------------- */
205UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
206    std::vector<run_t> runs;
207    std::vector<bitquad_t> quads;
208    const auto e1 = quad_end();
209    const auto e2 = other.quad_end();
210    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
211        const auto n = std::min(i1.length(), i2.length());
212        if ((i1.type() == Full) && (i2.type() == Full)) {
213            append_run(Full, n, runs);
214            i1 += n;
215            i2 += n;
216        }
217        else if ((i1.type() == Empty) || (i2.type() == Empty)) {
218            append_run(Empty, n, runs);
219            i1 += n;
220            i2 += n;
221        }
222        else if (i1.type() == Full) {
223            for (unsigned i = 0; i != n; ++i, ++i2) {
224                append_quad(i2.quad(), quads, runs);
225            }
226            i1 += n;
227        }
228        else if (i2.type() == Full) {
229            for (unsigned i = 0; i != n; ++i, ++i1) {
230                append_quad(i1.quad(), quads, runs);
231            }
232            i2 += n;
233        }
234        else { //both Mixed
235            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
236                append_quad(i1.quad() & i2.quad(), quads, runs);
237            }
238        }
239    }
240    return UnicodeSet(std::move(runs), std::move(quads));
241}
242
243/** ------------------------------------------------------------------------------------------------------------- *
244 * @brief union
245 ** ------------------------------------------------------------------------------------------------------------- */
246UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
247    std::vector<run_t> runs;
248    std::vector<bitquad_t> quads;
249    const auto e1 = quad_end();
250    const auto e2 = other.quad_end();
251    auto i1 = quad_begin(), i2 = other.quad_begin();
252    for (; i1 != e1 && i2 != e2; ) {
253        const auto n = std::min(i1.length(), i2.length());
254        if ((i1.type() == Empty) && (i2.type() == Empty)) {
255            append_run(Empty, n, runs);
256            i1 += n;
257            i2 += n;
258        } else if ((i1.type() == Full) || (i2.type() == Full)) {
259            append_run(Full, n, runs);
260            i1 += n;
261            i2 += n;
262        } else if (i1.type() == Empty) {
263            for (unsigned i = 0; i != n; ++i, ++i2) {
264                append_quad(i2.quad(), quads, runs);
265            }
266            i1 += n;
267        } else if (i2.type() == Empty) {
268            for (unsigned i = 0; i != n; ++i, ++i1) {
269                append_quad(i1.quad(), quads, runs);
270            }
271            i2 += n;
272        } else {
273            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
274                append_quad(i1.quad() | i2.quad(), quads, runs);
275            }
276        }
277    }
278    return UnicodeSet(std::move(runs), std::move(quads));
279}
280
281/** ------------------------------------------------------------------------------------------------------------- *
282 * @brief difference
283 ** ------------------------------------------------------------------------------------------------------------- */
284UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
285    std::vector<run_t> runs;
286    std::vector<bitquad_t> quads;
287    const auto e1 = quad_end();
288    const auto e2 = other.quad_end();
289    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
290        unsigned n = std::min(i1.length(), i2.length());
291        if ((i1.type() == Empty) || (i2.type() == Full) || (i1.type() == Full && i2.type() == Empty)) {
292            append_run(i1.type(), n, runs);
293            i1 += n;
294            i2 += n;
295        }
296        else if (i1.type() == Full) {
297            for (unsigned i = 0; i != n; ++i, ++i2) {
298                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
299            }
300            i1 += n;
301        }
302        else if (i2.type() == Empty) {
303            for (unsigned i = 0; i != n; ++i, ++i1) {
304                append_quad(i1.quad(), quads, runs);
305            }
306            i2 += n;
307        }
308        else {
309            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
310                append_quad(i1.quad() &~ i2.quad(), quads, runs);
311            }
312        }
313    }
314    return UnicodeSet(std::move(runs), std::move(quads));
315}
316
317/** ------------------------------------------------------------------------------------------------------------- *
318 * @brief symmetric difference
319 ** ------------------------------------------------------------------------------------------------------------- */
320UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
321    std::vector<run_t> runs;
322    std::vector<bitquad_t> quads;
323    const auto e1 = quad_end();
324    const auto e2 = other.quad_end();
325    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
326        unsigned n = std::min(i1.length(), i2.length());
327        if (i1.type() != Mixed && i2.type() != Mixed) {
328            append_run(i1.type() == i2.type() ? Empty : Full, n, runs);
329            i1 += n;
330            i2 += n;
331        }
332        else if (i1.type() == Empty) {
333            for (unsigned i = 0; i < n; ++i, ++i2) {
334                append_quad(i2.quad(), quads, runs);
335            }
336            i1 += n;
337        }
338        else if (i2.type() == Empty) {
339            for (unsigned i = 0; i < n; ++i, ++i1) {
340                append_quad(i1.quad(), quads, runs);
341            }
342            i2 += n;
343        }
344        else if (i1.type() == Full) {
345            for (unsigned i = 0; i < n; ++i, ++i2) {
346                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
347            }
348            i1 += n;
349        }
350        else if (i2.type() == Empty) {
351            for (unsigned i = 0; i < n; ++i, ++i1) {
352                append_quad(FULL_QUAD_MASK ^ i1.quad(), quads, runs);
353            }
354            i2 += n;
355        }
356        else {
357            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
358                append_quad(i1.quad() ^ i2.quad(), quads, runs);
359            }
360        }
361    }
362    return UnicodeSet(std::move(runs), std::move(quads));
363}
364
365/** ------------------------------------------------------------------------------------------------------------- *
366 * @brief equality
367 ** ------------------------------------------------------------------------------------------------------------- */
368bool UnicodeSet::operator==(const UnicodeSet & other) const {
369    if (mRuns.size() != other.mRuns.size() || mQuads.size() != other.mQuads.size()) {
370        return false;
371    }
372    for (auto i = mQuads.begin(), j = other.mQuads.begin(); i != mQuads.end(); ++i, ++j) {
373        if (*i != *j) return false;
374    }
375    for (auto i = mRuns.begin(), j = other.mRuns.begin(); i != mRuns.end(); ++i, ++j) {
376        if (*i != *j) return false;
377    }
378    return true;
379}
380
381/** ------------------------------------------------------------------------------------------------------------- *
382 * @brief less operator
383 ** ------------------------------------------------------------------------------------------------------------- */
384bool UnicodeSet::operator<(const UnicodeSet & other) const {
385    if (LLVM_LIKELY(mRuns.size() != other.mRuns.size())) {
386        return mRuns.size() < other.mRuns.size();
387    } else if (LLVM_LIKELY(mQuads.size() != other.mQuads.size())) {
388        return (mQuads.size() < other.mQuads.size());
389    } else { // equal run and quad lengths; test their individual values
390        for (auto ri = mRuns.cbegin(), end = mRuns.cend(), rj = other.mRuns.cbegin(); ri != end; ++ri, ++rj) {
391            if (*ri < *rj) {
392                return true;
393            } else if (*ri > *rj) {
394                return false;
395            }
396        }
397        for (auto qi = mQuads.cbegin(), end = mQuads.cend(), qj = other.mQuads.cbegin(); qi != end; ++qi, ++qj) {
398            if (*qi < *qj) {
399                return true;
400            } else if (*qi > *qj) {
401                return false;
402            }
403        }
404        return false;
405    }
406}
407
408/** ------------------------------------------------------------------------------------------------------------- *
409 * @brief insert
410 ** ------------------------------------------------------------------------------------------------------------- */
411void UnicodeSet::insert(const codepoint_t cp) {
412
413    if (LLVM_UNLIKELY(cp >= UNICODE_MAX)) {
414        throw std::runtime_error(std::to_string(cp) + " exceeds maximum code point.");
415    }
416
417    codepoint_t offset = cp / QUAD_BITS;
418    const bitquad_t value = static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK);
419    auto run = mRuns.begin();
420    auto quad = mQuads.begin();
421    length_t l = 0;
422    run_type_t t = Empty;
423    for (;;) {
424        std::tie(t, l) = *run;
425        if (offset < l) {
426            break;
427        }
428        if (t == Mixed) {
429            quad += l;
430        }
431        offset -= l;
432        ++run;
433    }
434    if (LLVM_LIKELY(t == Mixed)) {
435        quad += offset;
436        *quad |= value;
437        if (LLVM_LIKELY(*quad != FULL_QUAD_MASK)) {
438            assert (contains(cp));
439            return;
440        }
441        mQuads.erase(quad);
442    } else if (t == Empty) {
443        mQuads.insert(quad, value);
444    } else { // if (t == Full) {
445        assert (contains(cp));
446        return;
447    }
448    const unsigned remaining = l - (offset + 1);
449    if (offset == 0) {
450        *run = std::make_pair(t == Empty ? Mixed : Full, 1);
451        if (remaining != 0) {
452            mRuns.insert(++run, std::make_pair(t, remaining));
453        }
454    } else {
455        run->second = offset;
456        if (remaining == 0) {
457            mRuns.insert(++run, std::make_pair(t == Empty ? Mixed : Full, 1));
458        } else {
459            mRuns.insert(++run, {std::make_pair(t == Empty ? Mixed : Full, 1), std::make_pair(t, remaining)});
460        }
461    }
462
463    assert (verify(mRuns, mQuads));
464    assert (contains(cp));
465}
466
467/** ------------------------------------------------------------------------------------------------------------- *
468 * @brief insert_range
469 ** ------------------------------------------------------------------------------------------------------------- */
470void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi)  {
471
472    if (LLVM_UNLIKELY(lo > hi)) {
473        throw std::runtime_error('[' + std::to_string(lo) + ',' + std::to_string(hi) + "] is an illegal codepoint range!");
474    } else if (LLVM_UNLIKELY(hi > UNICODE_MAX)) {
475        throw std::runtime_error(std::to_string(hi) + " exceeds maximum code point.");
476    }
477
478    //this->dump(llvm::errs()); llvm::errs() << " + [" << lo << ',' << hi << "]\n"; llvm::errs().flush();
479
480    // Create a temporary run and quad set for the given range
481    std::vector<run_t> runs;
482    std::vector<bitquad_t> quads;
483
484    codepoint_t lo_index = lo / QUAD_BITS;
485    codepoint_t hi_index = hi / QUAD_BITS;
486
487    auto ri = mRuns.cbegin();
488    auto qi = mQuads.cbegin();
489
490    length_t length = 0;
491    run_type_t type = Empty;
492
493    // Advance past any full runs prior to the lo_index
494    for (;;) {
495        assert (ri != mRuns.cend());
496        std::tie(type, length) = *ri;
497        //llvm::errs() << std::distance(mRuns.cbegin(), ri) << ") type=" << (int)(type) << ", length=" << length << ", lo_index=" << lo_index << ", hi_index=" << hi_index << "\n"; llvm::errs().flush();
498        if (lo_index < length) {
499            break;
500        }
501        if (type == Mixed) {
502            assert (std::distance(qi, mQuads.cend()) >= length);
503            qi += length;
504        }
505        lo_index -= length;
506        hi_index -= length;
507        ++ri;
508    }
509
510    //llvm::errs() << "* " << std::distance(mRuns.cbegin(), ri) << ") type=" << (int)(type) << ", length=" << length << ", lo_index=" << lo_index << ", hi_index=" << hi_index << "\n"; llvm::errs().flush();
511
512    // Now record the runs and any quads prior to lo_index
513    runs.assign(mRuns.cbegin(), ri++);
514    if (lo_index) {
515        runs.push_back(std::make_pair(type, lo_index));
516        if (type == Mixed) {
517            assert (std::distance(qi, mQuads.cend()) >= lo_index);
518            qi += lo_index;
519        }
520        hi_index -= lo_index;
521        length -= lo_index;
522    }
523
524    quads.assign(mQuads.cbegin(), qi);
525    // We now have everything up to the first quad added to our temporary buffers; merge in the first new quad.
526    bitquad_t lo_quad = (FULL_QUAD_MASK << (lo & MOD_QUAD_BIT_MASK));
527    bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - (hi & MOD_QUAD_BIT_MASK)));
528
529    // If our original quad is full, just append a Full run
530    if (LLVM_UNLIKELY(type == Full)) {
531        append_run(Full, 1, runs);
532    } else { // Otherwise merge the new quad value with the original one
533        if (hi_index == 0) {
534            lo_quad &= hi_quad;
535        }
536        if (type == Mixed) {
537            assert (std::distance(qi, mQuads.cend()) > 0);
538            lo_quad |= *qi++;
539        }
540        append_quad(lo_quad, quads, runs);
541    }
542    --length;
543
544    //llvm::errs() << "* " << std::distance(mRuns.cbegin(), ri) << ") type=" << (int)(type) << ", length=" << length << ", lo_index=" << lo_index << ", hi_index=" << hi_index << "\n"; llvm::errs().flush();
545
546    // Now check if we need to write out any Full blocks between the lo and hi code points; adjust our position
547    // in the original quad to suit.
548    if (hi_index) {
549        // Add in any full runs between the lo and hi quads
550        append_run(Full, hi_index - 1, runs);
551        // Advance past original quads that were filled in
552        while (ri != mRuns.cend()) {
553            if (type == Mixed) {
554                assert (std::distance(qi, mQuads.cend()) >= length);
555                qi += length;
556            }
557            std::tie(type, length) = *ri++;
558            //llvm::errs() << std::distance(mRuns.cbegin(), ri) << ") type=" << (int)(type) << ", length=" << length << ", lo_index=" << lo_index << ", hi_index=" << hi_index << "\n"; llvm::errs().flush();
559            if (hi_index < length) {
560                break;
561            }
562            hi_index -= length;
563        }
564
565        // Write out the hi_quad value
566        if (LLVM_UNLIKELY(type == Full)) {
567            append_run(Full, 1, runs);
568        } else {
569            if (type == Mixed) {
570                assert (std::distance(qi, mQuads.cend()) > hi_index);
571                qi += hi_index;
572                hi_quad |= *qi++;
573            }
574            append_quad(hi_quad, quads, runs);
575        }
576    }
577
578    //llvm::errs() << "* " << std::distance(mRuns.cbegin(), ri) << ") type=" << (int)(type) << ", length=" << length << ", lo_index=" << lo_index << ", hi_index=" << hi_index << "\n";
579
580    //llvm::errs() << "* remaining=" << std::distance(ri, mRuns.cend()) << "\n";
581
582    //llvm::errs().flush();
583
584    // And append any remaining values from the original data
585    append_run(type, length - hi_index, runs);
586    assert ("We wrote all the runs but still have remaining quads?" && (ri != mRuns.cend() || qi == mQuads.cend()));
587    runs.insert(runs.end(), ri, mRuns.cend());
588    quads.insert(quads.end(), qi, mQuads.cend());
589    assert (verify(runs, quads));
590
591    mRuns.assign(runs.cbegin(), runs.cend());
592    mQuads.assign(quads.cbegin(), quads.cend());
593}
594
595/** ------------------------------------------------------------------------------------------------------------- *
596 * @brief contains
597 * @param codepoint
598 *
599 * Return whether this UnicodeSet contains the specified code point
600 ** ------------------------------------------------------------------------------------------------------------- */
601bool UnicodeSet::contains(const codepoint_t cp) const {
602    codepoint_t offset = cp / QUAD_BITS;
603    auto quad = mQuads.cbegin();
604    for (const auto r : mRuns) {
605        length_t l = 0;
606        run_type_t t = Empty;
607        std::tie(t, l) = r;
608        if (offset < l) {
609            if (t == Mixed) {
610                quad += offset;
611                return (*quad & static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK)) != 0;
612            }
613            return (t == Full);
614        }
615        if (t == Mixed) {
616            quad += l;
617        }       
618        offset -= l;
619    }
620    return false;
621}
622
623/** ------------------------------------------------------------------------------------------------------------- *
624 * @brief intersects
625 * @param lo_codepoint
626 * @param hi_codepoint
627 *
628 * Return true if this UnicodeSet contains any code point(s) between lo and hi (inclusive)
629 ** ------------------------------------------------------------------------------------------------------------- */
630bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const {
631    for (auto range : *this) {
632        if (range.second < lo) {
633            continue;
634        }
635        if (range.first > hi) {
636            break;
637        }
638        return true;
639    }
640    return false;
641}
642
643/** ------------------------------------------------------------------------------------------------------------- *
644 * @brief UnicodeSet::quad_iterator::advance
645 ** ------------------------------------------------------------------------------------------------------------- */
646void UnicodeSet::quad_iterator::advance(unsigned n) {
647    while (n > 0) {
648        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
649        if (remain > n) {
650            if (typeOf(*mRunIterator) == Mixed) {
651                mQuadIterator += n;
652            }
653            mOffset += n;
654            break;
655        }
656        if (typeOf(*mRunIterator) == Mixed) {
657            mQuadIterator += remain;
658        }
659        ++mRunIterator;
660        mOffset = 0;
661        n -= remain;
662    }
663}
664
665/** ------------------------------------------------------------------------------------------------------------- *
666 * @brief UnicodeSet::iterator::advance
667 ** ------------------------------------------------------------------------------------------------------------- */
668void UnicodeSet::iterator::advance(const unsigned n) {
669
670    assert (n == 1);
671
672    if (LLVM_UNLIKELY(mMinCodePoint >= 0x110000)) {
673        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
674    }
675
676    bool found = false;
677    // Find the start of our interval
678    while ( mBaseCodePoint < 0x110000 ) {
679        // Find the first non-empty block
680        if (typeOf(*mRunIterator) != Mixed) {           
681            // If we found a full run, this must be the start of our interval.
682            const auto baseCodePoint = mBaseCodePoint;
683            const auto type = typeOf(*mRunIterator);
684            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
685            if (type == Full) {
686                mMinCodePoint = baseCodePoint;
687                found = true;
688                break;
689            }
690        } else { // if (typeOf(t) == Mixed)
691            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
692                const bitquad_t m = (*mQuadIterator) & (FULL_QUAD_MASK << mQuadOffset);
693                // If we found a marker in m, it marks the beginning of our current interval.
694                // Find it and break out of the loop.
695                if (m) {
696                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
697                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
698                    found = true;
699                    break;
700                }
701                mBaseCodePoint += QUAD_BITS;
702                ++mQuadIterator;
703                ++mMixedRunIndex;
704                mQuadOffset = 0;
705            }
706            if (found) break;
707            ++mRunIterator;
708            mQuadOffset = 0;
709            mMixedRunIndex = 0;
710        }
711    }
712
713    if (!found) {
714        assert (mBaseCodePoint == 0x110000);
715        mMinCodePoint = 0x110000;
716        return;
717    }
718
719    // at this stage, the max code point is the previous max code point (initially 0)
720    assert (mMaxCodePoint <= mMinCodePoint);
721    found = false;
722    // Find the end of our interval
723    while ( mBaseCodePoint < 0x110000 ) {
724
725        // Find the first non-Full block
726        if (typeOf(*mRunIterator) != Mixed) {
727            // If this run is Empty, the max code point is the last computed base code point - 1.
728            const auto baseCodePoint = mBaseCodePoint;
729            const auto type = typeOf(*mRunIterator);
730            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
731            if (type == Empty) {
732                mMaxCodePoint = baseCodePoint - 1;
733                found = true;
734                break;
735            }
736        } else { // if (typeOf(t) == Mixed)
737            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
738                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
739
740                // If we found a marker in m, it marks the end of our current interval.
741                // Find it and break out of the loop.
742                if (m) {
743                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
744                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
745                    found = true;
746                    break;
747                }
748                mBaseCodePoint += QUAD_BITS;
749                ++mQuadIterator;
750                ++mMixedRunIndex;
751                mQuadOffset = 0;
752            }
753            if (found) break;
754            ++mRunIterator;
755            mQuadOffset = 0;
756            mMixedRunIndex = 0;
757        }
758    }
759    // if the very last block is a mixed block and we go past it, the last code point of the range is 0x10FFFF
760    if (!found) {
761        assert (mBaseCodePoint == 0x110000);
762        mMaxCodePoint = 0x10FFFF;
763    }
764
765    assert (mMinCodePoint <= mMaxCodePoint);
766}
767
768/** ------------------------------------------------------------------------------------------------------------- *
769 * @brief Empty Set Constructor
770 ** ------------------------------------------------------------------------------------------------------------- */
771UnicodeSet::UnicodeSet()
772: mRuns(mAllocator)
773, mQuads(mAllocator)
774{
775    append_run(Empty, UNICODE_QUAD_COUNT, mRuns);
776    assert (verify(mRuns, mQuads));
777}
778
779/** ------------------------------------------------------------------------------------------------------------- *
780 * @brief Singleton Set Constructor
781 ** ------------------------------------------------------------------------------------------------------------- */
782UnicodeSet::UnicodeSet(const codepoint_t codepoint)
783: mRuns(mAllocator)
784, mQuads(mAllocator)
785{
786    const codepoint_t quad_no = codepoint / QUAD_BITS;
787    append_run(Empty, quad_no, mRuns);
788    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
789    append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
790    assert (verify(mRuns, mQuads));
791}
792
793/** ------------------------------------------------------------------------------------------------------------- *
794 * @brief Range Set Constructor
795 ** ------------------------------------------------------------------------------------------------------------- */
796UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi)
797: mRuns(mAllocator)
798, mQuads(mAllocator)
799{
800    const codepoint_t lo_index = lo / QUAD_BITS;
801    const codepoint_t hi_index = hi / QUAD_BITS;
802    const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
803    const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
804    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
805    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
806    append_run(Empty, lo_index, mRuns);
807    bitquad_t mask = hi_quad;
808    if (lo_index == hi_index) {
809        mask &= lo_quad;
810    } else {
811        append_quad(lo_quad, mQuads, mRuns);
812        append_run(Full, hi_index - (lo_index + 1), mRuns);
813    }
814    append_quad(mask, mQuads, mRuns);
815    append_run(Empty, UNICODE_QUAD_COUNT - (hi_index + 1), mRuns);
816    assert (verify(mRuns, mQuads));
817}
818
819/** ------------------------------------------------------------------------------------------------------------- *
820 * @brief Range List Set Constructor
821 ** ------------------------------------------------------------------------------------------------------------- */
822template <typename itr>
823void convertIntervalRangesToSparseSet(const itr begin, const itr end, UnicodeSet::RunVector & mRuns, UnicodeSet::QuadVector & mQuads) {
824    assert (std::is_sorted(begin, end, [](const interval_t l, const interval_t r) {
825        assert (l.first <= l.second);
826        assert (l.second < UNICODE_MAX);
827        assert (r.first <= r.second);
828        assert (r.second < UNICODE_MAX);
829        return l.second < r.first;
830    }));
831
832    std::vector<run_t> runs;
833    std::vector<bitquad_t> quads;
834
835    codepoint_t prior_index = 0;
836    bitquad_t mask = 0;
837    for (auto interval = begin; interval != end; ) {
838        codepoint_t lo, hi;
839        std::tie(lo, hi) = *interval;
840        const codepoint_t lo_index = (lo / QUAD_BITS);
841        const codepoint_t hi_index = (hi / QUAD_BITS);
842        const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
843        const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
844        const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
845        const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
846        append_run(Empty, lo_index - prior_index, runs);
847        if (lo_index == hi_index) {
848            mask |= (lo_quad & hi_quad);
849        } else {
850            append_quad(mask | lo_quad, quads, runs);
851            append_run(Full, hi_index - (lo_index + 1), runs);
852            mask = hi_quad;
853        }
854        // if the next interval is in our current quad, continue to the next range
855        prior_index = hi_index;
856        if (LLVM_LIKELY(++interval != end)) {
857            if (hi_index == (interval->first / QUAD_BITS)) {
858                continue;
859            }
860        }
861        append_quad(mask, quads, runs);
862        mask = 0;
863        ++prior_index;
864    }
865    assert (mask == 0);
866    if (prior_index < UNICODE_QUAD_COUNT) {
867        append_run(Empty, UNICODE_QUAD_COUNT - prior_index, runs);
868    }   
869    assert (verify(runs, quads));
870    mRuns.assign(runs.begin(), runs.end());
871    mQuads.assign(quads.begin(), quads.end());
872}
873
874/** ------------------------------------------------------------------------------------------------------------- *
875 * @brief Interval Range Constructor
876 ** ------------------------------------------------------------------------------------------------------------- */
877UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end)
878: mRuns(0, {Empty, 0}, mAllocator)
879, mQuads(0, 0, mAllocator) {
880    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
881}
882
883/** ------------------------------------------------------------------------------------------------------------- *
884 * @brief Interval Range Constructor
885 ** ------------------------------------------------------------------------------------------------------------- */
886UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end)
887: mRuns(0, {Empty, 0}, mAllocator)
888, mQuads(0, 0, mAllocator) {
889    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
890}
891
892/** ------------------------------------------------------------------------------------------------------------- *
893 * @brief Copy Constructor
894 ** ------------------------------------------------------------------------------------------------------------- */
895UnicodeSet::UnicodeSet(const UnicodeSet & other)
896: mRuns(other.mRuns, mAllocator)
897, mQuads(other.mQuads, mAllocator) {
898    assert (verify(mRuns, mQuads));
899}
900
901/** ------------------------------------------------------------------------------------------------------------- *
902 * @brief Initializer Constructor
903 ** ------------------------------------------------------------------------------------------------------------- */
904UnicodeSet::UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q)
905: mRuns(r.begin(), r.end(), mAllocator)
906, mQuads(q.begin(), q.end(), mAllocator) {
907    assert (verify(mRuns, mQuads));
908}
909
910/** ------------------------------------------------------------------------------------------------------------- *
911 * @brief Internal Vector Constructor
912 ** ------------------------------------------------------------------------------------------------------------- */
913inline UnicodeSet::UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q)
914: mRuns(r.begin(), r.end(), mAllocator)
915, mQuads(q.begin(), q.end(), mAllocator) {
916    assert (verify(mRuns, mQuads));
917}
918
919}
Note: See TracBrowser for help on using the repository browser.