Changeset 5740 for icGREP


Ignore:
Timestamp:
Nov 18, 2017, 1:38:49 PM (14 months ago)
Author:
nmedfort
Message:

Bug fix for Grep Engine + better bug fix for UnicodeSet?

Location:
icGREP/icgrep-devel/icgrep
Files:
3 edited

Legend:

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

    r5739 r5740  
    141141}
    142142
    143 
    144143/** ------------------------------------------------------------------------------------------------------------- *
    145144 * @brief at
     
    152151        assert ((base % QUAD_BITS) == 0);
    153152        if (typeOf(r) == Empty) {
    154             base += QUAD_BITS * lengthOf(r);
     153            base += lengthOf(r) * QUAD_BITS;
    155154        } else if (typeOf(r) == Full) {
    156             const auto m = QUAD_BITS * lengthOf(r);
     155            const auto m = lengthOf(r) * QUAD_BITS;
    157156            if (LLVM_UNLIKELY(remaining < m)) {
    158157                return base + remaining;
     
    299298    const auto e2 = other.quad_end();
    300299    auto i1 = quad_begin(), i2 = other.quad_begin();
    301     while ((i1 != e1) && (i2 != e2)) {
     300    for (;;) {
     301        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
    302302        const auto n = std::min(i1.length(), i2.length());
     303        if (LLVM_UNLIKELY(n == 0)) {
     304            break;
     305        }
    303306        if ((i1.type() == Full) && (i2.type() == Full)) {
    304307            append_run(Full, n, runs);
     
    320323            i2 += n;
    321324        } else { // both Mixed
     325            assert (i1.type() == Mixed && i2.type() == Mixed);
    322326            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
    323327                append_quad(i1.quad() & i2.quad(), quads, runs);
     
    325329        }
    326330    }
     331    assert (i1 == e1 && i2 == e2);
    327332    return UnicodeSet(std::move(runs), std::move(quads));
    328333}
     
    337342    const auto e2 = other.quad_end();
    338343    auto i1 = quad_begin(), i2 = other.quad_begin();
    339     while ((i1 != e1) && (i2 != e2)) {
     344    for (;;) {
     345        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
    340346        const auto n = std::min(i1.length(), i2.length());
     347        if (LLVM_UNLIKELY(n == 0)) {
     348            break;
     349        }
    341350        if ((i1.type() == Empty) && (i2.type() == Empty)) {
    342351            append_run(Empty, n, runs);
     
    348357            i2 += n;
    349358        } else if (i1.type() == Empty) {
     359            assert (i2.type() == Mixed);
    350360            for (unsigned i = 0; i != n; ++i, ++i2) {
    351361                append_quad(i2.quad(), quads, runs);
     
    353363            i1 += n;
    354364        } else if (i2.type() == Empty) {
     365            assert (i1.type() == Mixed);
    355366            for (unsigned i = 0; i != n; ++i, ++i1) {
    356367                append_quad(i1.quad(), quads, runs);
     
    358369            i2 += n;
    359370        } else { // both Mixed
     371            assert (i1.type() == Mixed && i2.type() == Mixed);
    360372            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
    361373                append_quad(i1.quad() | i2.quad(), quads, runs);
     
    363375        }
    364376    }
    365     // append any remaining blocks
    366     if ((i1 != e1) || (i2 != e2)) {
    367         assert ((i1 != e1) ^ (i2 != e2));
    368         auto i3 = (i1 != e1) ? i1 : i2;
    369         const auto e3 = (i1 != e1) ? e1 : e2;       
    370         while (i3 != e3) {
    371             const auto n = i3.length();
    372             if (i3.type() == Empty || i3.type() == Full) {
    373                 append_run(i3.type(), n, runs);
    374                 i3 += n;
    375             } else {
    376                 for (unsigned i = 0; i != n; ++i3) {
    377                     append_quad(i3.quad(), quads, runs);
    378                 }
    379             }           
    380         }
    381     }
     377   
     378    assert (i1 == e1 && i2 == e2);
    382379    return UnicodeSet(std::move(runs), std::move(quads));
    383380}
     
    392389    const auto e2 = other.quad_end();
    393390    auto i1 = quad_begin(), i2 = other.quad_begin();
    394     while ((i1 != e1) && (i2 != e2)) {
    395         unsigned n = std::min(i1.length(), i2.length());
     391    for (;;) {
     392        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
     393        const auto n = std::min(i1.length(), i2.length());
     394        assert (n != 0 || (i1 == e1 && i2 == e2));
     395        if (LLVM_UNLIKELY(n == 0)) {
     396            break;
     397        }
    396398        if ((i1.type() == Empty) || (i2.type() == Full)) {           
    397399            append_run(Empty, n, runs);
     
    413415            }
    414416            i2 += n;
    415         } else {           
     417        } else { // both Mixed
     418            assert (i1.type() == Mixed && i2.type() == Mixed);
    416419            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {               
    417420                append_quad(i1.quad() &~ i2.quad(), quads, runs);
     
    419422        }
    420423    }
    421     while (i1 != e1) {
    422         const auto n = i1.length();
    423         if (i1.type() == Empty || i1.type() == Full) {
    424             append_run(i1.type(), n, runs);
    425             i1 += n;
    426         } else {
    427             for (unsigned i = 0; i != n; ++i1) {
    428                 append_quad(i1.quad(), quads, runs);
    429             }
    430         }           
    431     }
     424    assert (i1 == e1 && i2 == e2);
    432425    return UnicodeSet(std::move(runs), std::move(quads));
    433426}
     
    442435    const auto e2 = other.quad_end();
    443436    auto i1 = quad_begin(), i2 = other.quad_begin();
    444     while ((i1 != e1) && (i2 != e2)) {
    445         unsigned n = std::min(i1.length(), i2.length());
     437    for (;;) {
     438        assert ("neither run can be zero length unless both are of zero length" && ((i1.length() != 0) ^ (i2.length() == 0)));
     439        const auto n = std::min(i1.length(), i2.length());
     440        if (LLVM_UNLIKELY(n == 0)) {
     441            break;
     442        }
    446443        if (i1.type() != Mixed && i2.type() != Mixed) {
    447444            append_run(i1.type() == i2.type() ? Empty : Full, n, runs);
     
    468465            }
    469466            i2 += n;
    470         } else {
     467        } else { // both Mixed
     468            assert (i1.type() == Mixed && i2.type() == Mixed);
    471469            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
    472470                append_quad(i1.quad() ^ i2.quad(), quads, runs);
     
    474472        }
    475473    }
    476     // append any remaining blocks
    477     if ((i1 != e1) || (i2 != e2)) {
    478         assert ((i1 != e1) ^ (i2 != e2));
    479         auto i3 = (i1 != e1) ? i1 : i2;
    480         const auto e3 = (i1 != e1) ? e1 : e2;       
    481         while (i3 != e3) {
    482             const auto n = i3.length();
    483             if (i3.type() == Empty || i3.type() == Full) {
    484                 append_run(i3.type(), n, runs);
    485                 i3 += n;
    486             } else {
    487                 for (unsigned i = 0; i != n; ++i3) {
    488                     append_quad(i3.quad(), quads, runs);
    489                 }
    490             }           
    491         }
    492     }
     474    assert (i1 == e1 && i2 == e2);
    493475    return UnicodeSet(std::move(runs), std::move(quads));
    494476}
     
    761743/** ------------------------------------------------------------------------------------------------------------- *
    762744 * @brief intersects
    763  * @param other_set
     745 * @param other
    764746 *
    765  * Return true if this UnicodeSet has a non-empty intersection with other_set
     747 * Return true if this UnicodeSet has a non-empty intersection with other
    766748 ** ------------------------------------------------------------------------------------------------------------- */
    767749bool UnicodeSet::intersects(const UnicodeSet & other) const {
    768     const auto e1 = quad_end();
    769     const auto e2 = other.quad_end();
    770     for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
     750    for (auto i1 = quad_begin(), i2 = other.quad_begin();; ) {
    771751        auto n = std::min(i1.length(), i2.length());
     752        if (LLVM_UNLIKELY(n == 0)) {
     753            return false;
     754        }
    772755        if (i1.type() == Empty || i2.type() == Empty) {
    773756            i1 += n;
     
    781764        }
    782765    }
    783     return false;
    784766}
    785767
     
    790772void UnicodeSet::quad_iterator::advance(unsigned n) {
    791773    while (n > 0) {
    792         const unsigned remain = lengthOf(*mRunIterator) - mOffset;
    793         if (remain > n) {
    794             if (typeOf(*mRunIterator) == Mixed) {
     774        assert (mRemaining > 0);
     775        if (mRemaining > n) {
     776            if (mType == Mixed) {
     777                assert (mQuadIterator <= (mQuadEnd - n));
    795778                mQuadIterator += n;
    796779            }
    797             mOffset += n;
     780            mRemaining -= n;
    798781            break;
    799782        }
    800         if (typeOf(*mRunIterator) == Mixed) {
    801             mQuadIterator += remain;
    802         }
     783        if (mType == Mixed) {
     784            assert (mQuadIterator <= (mQuadEnd - mRemaining));
     785            mQuadIterator += mRemaining;
     786        }
     787        n -= mRemaining;       
    803788        ++mRunIterator;
    804         mOffset = 0;
    805         n -= remain;
    806     }
     789        if (LLVM_UNLIKELY(mRunIterator == mRunEnd)) {
     790            mType = Empty;
     791            mRemaining = 0;
     792            break;
     793        }
     794        mType = typeOf(*mRunIterator);
     795        mRemaining = lengthOf(*mRunIterator);
     796    }
     797    assert ("remaining length cannot be 0 unless this is the final run" && ((mRunIterator != mRunEnd) || (mRemaining == 0)));
     798    assert ("cannot be the final quad unless this is the final run" && ((mRunIterator != mRunEnd) || (mQuadIterator == mQuadEnd)));
    807799}
    808800
     
    10631055
    10641056}
     1057
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.h

    r5739 r5740  
    159159        friend class boost::iterator_core_access;
    160160    public:
    161         quad_iterator(RunIterator runIterator, QuadIterator quadIterator)
    162             : mRunIterator(runIterator), mQuadIterator(quadIterator), mOffset(0) {}
     161        quad_iterator(RunIterator runIterator, RunIterator runEnd, QuadIterator quadIterator, QuadIterator quadEnd, const run_type_t type, const length_t remaining)
     162        : mRunIterator(runIterator)
     163        , mRunEnd(runEnd)
     164        , mQuadIterator(quadIterator)
     165        #ifndef NDEBUG
     166        , mQuadEnd(quadEnd)
     167        #endif
     168        , mType(type)
     169        , mRemaining(remaining) {}
    163170
    164171        void advance(unsigned n);
     
    173180
    174181        inline run_type_t type() const {
    175             return mRunIterator->first;
     182            return mType;
    176183        }
    177184
    178185        inline length_t length() const {
    179             return mRunIterator->second - mOffset;
     186            return mRemaining;
    180187        }
    181188
    182189        inline bitquad_t quad() const {
     190            assert (mQuadIterator != mQuadEnd);
    183191            return *mQuadIterator;
    184192        }
    185193
    186194        inline bool equal(const quad_iterator & other) const {
    187             return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator);
     195            const auto r = (mRunIterator == other.mRunIterator) && (mRemaining == other.mRemaining);
     196            assert (!r || (mQuadIterator == other.mQuadIterator));
     197            return r;
    188198        }
    189199
    190200    private:
    191         RunIterator     mRunIterator;
    192         QuadIterator    mQuadIterator;
    193         unsigned        mOffset;
     201        RunIterator         mRunIterator;   
     202        const RunIterator   mRunEnd;
     203        QuadIterator        mQuadIterator;       
     204        #ifndef NDEBUG
     205        const QuadIterator  mQuadEnd;
     206        #endif
     207        run_type_t          mType;
     208        length_t            mRemaining;
    194209    };
    195210
    196211    inline quad_iterator quad_begin() const {
    197         return quad_iterator(mRuns.cbegin(), mQuads.cbegin());
     212        return quad_iterator(mRuns.cbegin(), mRuns.cend(), mQuads.cbegin(), mQuads.cend(), std::get<0>(*mRuns.cbegin()), std::get<1>(*mRuns.cbegin()));
    198213    }
    199214
    200215    inline quad_iterator quad_end() const {
    201         return quad_iterator(mRuns.cend(), mQuads.cend());
     216        return quad_iterator(mRuns.cend(), mRuns.cend(), mQuads.cend(), mQuads.cend(), Empty, 0);
    202217    }
    203218
  • icGREP/icgrep-devel/icgrep/grep_engine.cpp

    r5735 r5740  
    381381    if (fileDescriptor == -1) return 0;
    382382    EmitMatch accum(linePrefix(fileName), mResultStrs[fileIdx].get());
    383     uint64_t grepResult = f(fileDescriptor, reinterpret_cast<intptr_t>(&accum));
     383    f(fileDescriptor, reinterpret_cast<intptr_t>(&accum));
    384384    close(fileDescriptor);
    385385    if (accum.mLineCount > 0) grepMatchFound = true;
     
    424424   
    425425void * DoGrepThreadFunction(void *args) {
    426     reinterpret_cast<GrepEngine *>(args)->DoGrepThreadMethod();
     426    return reinterpret_cast<GrepEngine *>(args)->DoGrepThreadMethod();
    427427}
    428428
     
    482482    count_mutex.lock();
    483483    fileIdx = mNextFileToPrint;
    484     bool readyToPrint = ((fileIdx == 0) || (mFileStatus[fileIdx-1] == FileStatus::PrintComplete)) && (mFileStatus[fileIdx] == FileStatus::GrepComplete);
     484    bool readyToPrint = ((fileIdx == 0) || (mFileStatus[fileIdx - 1] == FileStatus::PrintComplete)) && (mFileStatus[fileIdx] == FileStatus::GrepComplete);
    485485    if (fileIdx < inputFiles.size() && readyToPrint) {
    486486        mFileStatus[fileIdx] = FileStatus::Printing;
     
    488488    }
    489489    count_mutex.unlock();
     490
    490491    while (fileIdx < inputFiles.size()) {
    491492        if (readyToPrint) {
    492493            std::cout << mResultStrs[fileIdx]->str();
    493         }
    494         else if (pthread_self() == mEngineThread) {
     494        } else if (pthread_self() == mEngineThread) {
    495495            mGrepDriver->performIncrementalCacheCleanupStep();
    496496        }
     
    498498        if (readyToPrint) mFileStatus[fileIdx] = FileStatus::PrintComplete;
    499499        fileIdx = mNextFileToPrint;
    500         readyToPrint = (mFileStatus[fileIdx-1] == FileStatus::PrintComplete) && (mFileStatus[fileIdx] == FileStatus::GrepComplete);
    501         if (fileIdx < inputFiles.size() && readyToPrint) {
    502             mFileStatus[fileIdx] = FileStatus::Printing;
    503             mNextFileToPrint++;
     500        if (fileIdx < inputFiles.size()) {
     501            readyToPrint = ((fileIdx == 0) || (mFileStatus[fileIdx - 1] == FileStatus::PrintComplete)) && (mFileStatus[fileIdx] == FileStatus::GrepComplete);
     502            if (readyToPrint) {
     503                mFileStatus[fileIdx] = FileStatus::Printing;
     504                mNextFileToPrint++;
     505            }
    504506        }
    505507        count_mutex.unlock();
     
    512514    }
    513515}
    514 }
    515 
     516
     517}
     518
Note: See TracChangeset for help on using the changeset viewer.