Ignore:
Timestamp:
Oct 2, 2014, 3:22:19 PM (5 years ago)
Author:
nmedfort
Message:

Performance bug fix

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/re/re_simplifier.cpp

    r4194 r4203  
    1515RE * RE_Simplifier::simplify(RE * re) {
    1616    if (Alt * alt = dyn_cast<Alt>(re)) {
    17         for (auto i = alt->begin(); i != alt->end(); ++i) {
    18             *i = simplify(*i);
     17        std::vector<RE*> list;
     18        list.reserve(alt->size());
     19        for (RE * re : *alt) {
     20            list.push_back(simplify(re));
    1921        }
    20         re = simplify(alt);
     22        re = makeAlt(list.begin(), list.end());
    2123    }
    2224    else if (Seq * seq = dyn_cast<Seq>(re)) {
    23         for (auto i = seq->begin(); i != seq->end(); ++i) {
    24             *i = simplify(*i);
     25        std::vector<RE*> list;
     26        list.reserve(seq->size());
     27        for (RE * re : *seq) {
     28            list.push_back(simplify(re));
    2529        }
    26         re = simplify(seq);
     30        re = makeSeq(seq->getType(), list.begin(), list.end());
    2731    }
    2832    else if (Rep * rep = dyn_cast<Rep>(re)) {
    29         rep->setRE(simplify(rep->getRE()));
    30         simplify(rep);
     33        re = makeRep(simplify(rep->getRE()), rep->getLB(), rep->getUB());
    3134    }
    3235    return re;
    3336}
    3437
    35 RE * RE_Simplifier::simplify(Seq * seq) {
    36     /*
    37       mkSeq - make a sequence, but flatten.  Result might not be a Seq. If
    38       there is only one component for a sequence, simply return that.
    39     */
    40 
    41     RE * re = seq;
    42     if (!seq->empty()) {
    43         std::vector<RE*> list;
    44         list.reserve(seq->size());
    45         // Reverse the order of the input list so we can more efficiently "pull" the first
    46         // character from the end. Note: this uses a linear inplace reversal.
    47         std::reverse(seq->begin(), seq->end());
    48 
    49         while (!seq->empty()) {
    50             RE * next = seq->back();
    51             seq->pop_back();
    52             if (Seq * re_seq = dyn_cast<Seq>(next)) {
    53                 if (re_seq->getType() != Seq::Type::Byte) {
    54                     // like above, insert the "subsequence" to flatten in reverse order
    55                     std::reverse_copy(re_seq->begin(), re_seq->end(), std::back_inserter(*seq));
    56                     re_seq->clear();
    57                     delete re_seq;
    58                     continue;
    59                 }
    60             }
    61             list.push_back(next);
    62         }
    63         if (list.size() == 1) {
    64             re = list.back();
    65             delete seq;
    66         }
    67         else {
    68             seq->swap(list);
    69         }
    70     }
    71     return re;
    7238}
    73 
    74 /**
    75  * @brief makeAlt
    76  *
    77  * Build an Alt, flattening alternative subgroups, and combining character classes and
    78  * move character classes towards the end of the list to ensure that all combinations are found.
    79  *
    80  * @param list
    81  * @return simplified RE representing the Alt
    82  */
    83 RE * RE_Simplifier::simplify(Alt * alt) {
    84     RE * re = alt;
    85     if (!alt->empty()) {
    86 
    87         std::queue<CC*> ccs;
    88 
    89         std::vector<RE *> list;
    90         while (!alt->empty()) {
    91             RE * next = alt->back();
    92             alt->pop_back();
    93             if (Alt * re_alt = dyn_cast<Alt>(next)) {
    94                 alt->insert(alt->end(), re_alt->begin(), re_alt->end());
    95                 re_alt->clear();
    96                 delete re_alt;
    97             }
    98             else if (CC * cc = dyn_cast<CC>(next)) {
    99                 ccs.push(cc);
    100             }
    101             else {
    102                 list.push_back(next);
    103             }
    104         }
    105 
    106         if (!ccs.empty()) {
    107             while (ccs.size() > 1) {
    108                 CC * a = ccs.front(); ccs.pop();
    109                 CC * b = ccs.front(); ccs.pop();
    110                 ccs.push(makeCC(a, b));
    111             }
    112             list.push_back(ccs.front());
    113         }
    114 
    115         if (list.size() == 1) {
    116             // if only one alternation exists, discard the Alt object itself and return the internal RE.
    117             re = list.back();
    118             delete alt;
    119         }
    120         else {
    121             alt->swap(list);
    122         }
    123     }
    124     return re;
    125 }
    126 
    127 RE * RE_Simplifier::simplify(Rep * rep) {
    128     RE * re = rep->getRE();
    129     const int lb = rep->getLB();
    130     const int ub = rep->getUB();
    131     std::unique_ptr<Rep> janitor(rep);
    132     rep->setRE(nullptr);
    133     if (Rep * nrep = dyn_cast<Rep>(re)) {
    134         if (nrep->getUB() == Rep::UNBOUNDED_REP) {
    135             if ((lb > 0) || (nrep->getLB() <= 1)) {
    136                 nrep->setLB(nrep->getLB() * lb);
    137                 nrep->setUB(Rep::UNBOUNDED_REP);
    138                 return simplify(nrep);
    139             }
    140             else if (lb == 0) {
    141                 nrep->setLB(0);
    142                 nrep->setUB(1);
    143                 return simplify(nrep);
    144             }
    145         }
    146         else if ((nrep->getUB() * lb) >= (nrep->getLB() * (lb + 1) - 1)) {
    147             nrep->setLB(nrep->getUB() * lb);
    148             nrep->setUB(ubCombine(nrep->getUB(), ub));
    149             return simplify(nrep);
    150         }
    151     }
    152     else {
    153         if (Seq * seq = dyn_cast<Seq>(re)) {
    154             if (seq->empty()) {
    155                 return seq;
    156             }
    157         }
    158         if ((lb == 0) && (ub == 0)) {
    159             delete re;
    160             return makeSeq();
    161         }
    162         else if ((lb == 1) && (ub == 1)) {
    163             return re;
    164         }
    165     }
    166     rep->setRE(re);
    167     return janitor.release();
    168 }
    169 
    170 inline int RE_Simplifier::ubCombine(const int h1, const int h2) {
    171     if ((h1 == Rep::UNBOUNDED_REP) || (h2 == Rep::UNBOUNDED_REP)) {
    172         return Rep::UNBOUNDED_REP;
    173     }
    174     else {
    175         return h1 * h2;
    176     }
    177 }
    178 
    179 }
Note: See TracChangeset for help on using the changeset viewer.