From debbugs-submit-bounces@debbugs.gnu.org Sat Apr 12 02:10:38 2014 Received: (at submit) by debbugs.gnu.org; 12 Apr 2014 06:10:38 +0000 Received: from localhost ([127.0.0.1]:45957 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WYr9B-00081Z-Kw for submit@debbugs.gnu.org; Sat, 12 Apr 2014 02:10:38 -0400 Received: from eggs.gnu.org ([208.118.235.92]:55241) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WYr97-00081A-SP for submit@debbugs.gnu.org; Sat, 12 Apr 2014 02:10:34 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WYr8u-0006C5-0N for submit@debbugs.gnu.org; Sat, 12 Apr 2014 02:10:28 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:45451) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WYr8t-0006C1-T9 for submit@debbugs.gnu.org; Sat, 12 Apr 2014 02:10:19 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:56944) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WYr8m-00035A-50 for bug-grep@gnu.org; Sat, 12 Apr 2014 02:10:19 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WYr8e-0005xB-DK for bug-grep@gnu.org; Sat, 12 Apr 2014 02:10:11 -0400 Received: from mailgw04.kcn.ne.jp ([61.86.7.211]:59678) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WYr8d-0005vF-Ue for bug-grep@gnu.org; Sat, 12 Apr 2014 02:10:04 -0400 Received: from imp01 (mailgw5.kcn.ne.jp [61.86.15.231]) by mailgw04.kcn.ne.jp (Postfix) with ESMTP id C14F36C1E8A for ; Sat, 12 Apr 2014 15:10:02 +0900 (JST) Received: from mail07.kcn.ne.jp ([61.86.6.186]) by imp01 with bizsmtp id ouA21n00g40oyB901uA2Q0; Sat, 12 Apr 2014 15:10:02 +0900 X-OrgRCPT: bug-grep@gnu.org Received: from [10.120.1.47] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail07.kcn.ne.jp (Postfix) with ESMTPA id 62FB1D50020 for ; Sat, 12 Apr 2014 15:10:02 +0900 (JST) Date: Sat, 12 Apr 2014 15:10:02 +0900 From: Norihiro Tanaka To: bug-grep@gnu.org Subject: [PATCH] grep: waste of a lot of memory for a large pattern in dfamust Message-Id: <20140412151001.2C0C.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5348D690000000002C12_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.0 (----) --------_5348D690000000002C12_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit dfamust() uses a log of memory for long pattern. $ echo abc | grep -f /usr/share/dict/words /usr/share/dict/words is about 5MB. However, dfamust() will require memory over 100MB. Norihiro --------_5348D690000000002C12_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="patch.txt" Content-Disposition: attachment; filename="patch.txt" Content-Transfer-Encoding: base64 RnJvbSA1N2U3YmRjNWE3ZDllY2YzZWZlZjk3OTExMjMxNzg5NGNmMjZkOGJkIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTYXQsIDEyIEFwciAyMDE0IDE0OjIwOjExICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZ3Jl cDogd2FzdGUgb2YgYSBsb3Qgb2YgbWVtb3J5IGZvciBhIGxhcmdlIHBhdHRlcm4gaW4gZGZhbXVz dAoKKiBzcmMvZGZhLmMgKHN0cnVjdCBtdXN0KTogTmV3IG1lbWJlciBgcHJldicuICBJdCBoYXMg dGhlIHBvaW50ZXIgdG8KcHJldmlvdXMgbXVzdC4KKGFsbG9jbXVzdCk6IE5ldyBmdW5jdGlvbi4K KGZyZWVtdXN0KTogTmV3IGZ1bmN0aW9uLgooZGZhbXVzdCk6IFVzZSBpdC4KLS0tCiBzcmMvZGZh LmMgfCAxMjUgKysrKysrKysrKysrKysrKysrKysrKysrKysrKystLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0KIDEgZmlsZSBjaGFuZ2VkLCA1OCBpbnNlcnRpb25zKCspLCA2NyBkZWxl dGlvbnMoLSkKCmRpZmYgLS1naXQgYS9zcmMvZGZhLmMgYi9zcmMvZGZhLmMKaW5kZXggMmI2YzVk Ni4uOTI2OGZhYSAxMDA2NDQKLS0tIGEvc3JjL2RmYS5jCisrKyBiL3NyYy9kZmEuYwpAQCAtNDAx MiwxMyArNDAxMiwzMCBAQCBpbmJvdGggKGNoYXIgKipsZWZ0LCBjaGFyICoqcmlnaHQpCiAgIHJl dHVybiBib3RoOwogfQogCi10eXBlZGVmIHN0cnVjdAordHlwZWRlZiBzdHJ1Y3QgbXVzdCBtdXN0 OworCitzdHJ1Y3QgbXVzdAogewogICBjaGFyICoqaW47CiAgIGNoYXIgKmxlZnQ7CiAgIGNoYXIg KnJpZ2h0OwogICBjaGFyICppczsKLX0gbXVzdDsKKyAgbXVzdCAqcHJldjsKK307CisKK3N0YXRp YyBtdXN0ICoKK2FsbG9jbXVzdCAobXVzdCAqcHJldikKK3sKKyAgbXVzdCAqbXAgPSB4bWFsbG9j IChzaXplb2YgKnByZXYpOworICBtcC0+aW4gPSB4bWFsbG9jIChzaXplb2YgKm1wLT5pbik7Cisg IG1wLT5sZWZ0ID0geG1hbGxvYyAoMik7CisgIG1wLT5yaWdodCA9IHhtYWxsb2MgKDIpOworICBt cC0+aXMgPSB4bWFsbG9jICgyKTsKKyAgbXAtPmxlZnRbMF0gPSBtcC0+cmlnaHRbMF0gPSBtcC0+ aXNbMF0gPSAnXDAnOworICBtcC0+aW5bMF0gPSBOVUxMOworICBtcC0+cHJldiA9IHByZXY7Cisg IHJldHVybiBtcDsKK30KIAogc3RhdGljIHZvaWQKIHJlc2V0bXVzdCAobXVzdCAqIG1wKQpAQCAt NDAyOCw0MiArNDA0NSwzMCBAQCByZXNldG11c3QgKG11c3QgKiBtcCkKIH0KIAogc3RhdGljIHZv aWQKK2ZyZWVtdXN0IChtdXN0ICptcCkKK3sKKyAgZnJlZWxpc3QgKG1wLT5pbik7CisgIGZyZWUg KG1wLT5pbik7CisgIGZyZWUgKG1wLT5sZWZ0KTsKKyAgZnJlZSAobXAtPnJpZ2h0KTsKKyAgZnJl ZSAobXAtPmlzKTsKKyAgZnJlZSAobXApOworfQorCitzdGF0aWMgdm9pZAogZGZhbXVzdCAoc3Ry dWN0IGRmYSAqZCkKIHsKLSAgbXVzdCAqbXVzdHM7Ci0gIG11c3QgKm1wOworICBtdXN0ICptcCA9 IE5VTEw7CiAgIGNoYXIgKnJlc3VsdDsKICAgc2l6ZV90IHJpOwogICBzaXplX3QgaTsKICAgYm9v bCBleGFjdDsKLSAgc3RhdGljIG11c3QgbXVzdDA7CiAgIHN0cnVjdCBkZmFtdXN0ICpkbTsKICAg c3RhdGljIGNoYXIgZW1wdHlfc3RyaW5nW10gPSAiIjsKIAogICByZXN1bHQgPSBlbXB0eV9zdHJp bmc7CiAgIGV4YWN0ID0gZmFsc2U7Ci0gIE1BTExPQyAobXVzdHMsIGQtPnRpbmRleCArIDEpOwot ICBtcCA9IG11c3RzOwotICBmb3IgKGkgPSAwOyBpIDw9IGQtPnRpbmRleDsgKytpKQotICAgIG1w W2ldID0gbXVzdDA7Ci0gIGZvciAoaSA9IDA7IGkgPD0gZC0+dGluZGV4OyArK2kpCi0gICAgewot ICAgICAgbXBbaV0uaW4gPSB4bWFsbG9jIChzaXplb2YgKm1wW2ldLmluKTsKLSAgICAgIG1wW2ld LmxlZnQgPSB4bWFsbG9jICgyKTsKLSAgICAgIG1wW2ldLnJpZ2h0ID0geG1hbGxvYyAoMik7Ci0g ICAgICBtcFtpXS5pcyA9IHhtYWxsb2MgKDIpOwotICAgICAgbXBbaV0ubGVmdFswXSA9IG1wW2ld LnJpZ2h0WzBdID0gbXBbaV0uaXNbMF0gPSAnXDAnOwotICAgICAgbXBbaV0uaW5bMF0gPSBOVUxM OwotICAgIH0KLSNpZmRlZiBERUJVRwotICBmcHJpbnRmIChzdGRlcnIsICJkZmFtdXN0OlxuIik7 Ci0gIGZvciAoaSA9IDA7IGkgPCBkLT50aW5kZXg7ICsraSkKLSAgICB7Ci0gICAgICBmcHJpbnRm IChzdGRlcnIsICIgJXpkOiIsIGkpOwotICAgICAgcHJ0b2sgKGQtPnRva2Vuc1tpXSk7Ci0gICAg fQotICBwdXRjICgnXG4nLCBzdGRlcnIpOwotI2VuZGlmCisKICAgZm9yIChyaSA9IDA7IHJpIDwg ZC0+dGluZGV4OyArK3JpKQogICAgIHsKICAgICAgIHRva2VuIHQgPSBkLT50b2tlbnNbcmldOwpA QCAtNDA3MywxMSArNDA3OCw2IEBAIGRmYW11c3QgKHN0cnVjdCBkZmEgKmQpCiAgICAgICAgIGNh c2UgUlBBUkVOOgogICAgICAgICAgIGFzc2VydCAoISJuZWl0aGVyIExQQVJFTiBub3IgUlBBUkVO IG1heSBhcHBlYXIgaGVyZSIpOwogCi0gICAgICAgIGNhc2UgU1RBUjoKLSAgICAgICAgY2FzZSBR TUFSSzoKLSAgICAgICAgICBhc3NlcnQgKG11c3RzIDwgbXApOwotICAgICAgICAgIC0tbXA7Ci0g ICAgICAgICAgLyogRmFsbCB0aHJvdWdoLiAgKi8KICAgICAgICAgY2FzZSBFTVBUWToKICAgICAg ICAgY2FzZSBCRUdMSU5FOgogICAgICAgICBjYXNlIEVORExJTkU6CkBAIC00MDg4LDE5ICs0MDg4 LDI0IEBAIGRmYW11c3QgKHN0cnVjdCBkZmEgKmQpCiAgICAgICAgIGNhc2UgQkFDS1JFRjoKICAg ICAgICAgY2FzZSBBTllDSEFSOgogICAgICAgICBjYXNlIE1CQ1NFVDoKKyAgICAgICAgICBtcCA9 IGFsbG9jbXVzdCAobXApOworICAgICAgICAgIC8qIEZhbGwgdGhyb3VnaC4gICovCisgICAgICAg IGNhc2UgU1RBUjoKKyAgICAgICAgY2FzZSBRTUFSSzoKKyAgICAgICAgICBhc3NlcnQgKG1wICE9 IE5VTEwpOwogICAgICAgICAgIHJlc2V0bXVzdCAobXApOwogICAgICAgICAgIGJyZWFrOwogCiAg ICAgICAgIGNhc2UgT1I6Ci0gICAgICAgICAgYXNzZXJ0ICgmbXVzdHNbMl0gPD0gbXApOworICAg ICAgICAgIGFzc2VydCAobXAgJiYgbXAtPnByZXYpOwogICAgICAgICAgIHsKICAgICAgICAgICAg IGNoYXIgKipuZXc7CiAgICAgICAgICAgICBtdXN0ICpsbXA7CiAgICAgICAgICAgICBtdXN0ICpy bXA7CiAgICAgICAgICAgICBzaXplX3QgaiwgbG4sIHJuLCBuOwogCi0gICAgICAgICAgICBybXAg PSAtLW1wOwotICAgICAgICAgICAgbG1wID0gLS1tcDsKKyAgICAgICAgICAgIHJtcCA9IG1wOwor ICAgICAgICAgICAgbG1wID0gbXAgPSBtcC0+cHJldjsKICAgICAgICAgICAgIC8qIEd1YXJhbnRl ZWQgdG8gYmUuICBVbmxpa2VseSwgYnV0IC4uLiAgKi8KICAgICAgICAgICAgIGlmICghU1RSRVEg KGxtcC0+aXMsIHJtcC0+aXMpKQogICAgICAgICAgICAgICBsbXAtPmlzWzBdID0gJ1wwJzsKQEAg LTQxMjcsMzIgKzQxMzIsMzUgQEAgZGZhbXVzdCAoc3RydWN0IGRmYSAqZCkKICAgICAgICAgICAg IGZyZWVsaXN0IChsbXAtPmluKTsKICAgICAgICAgICAgIGZyZWUgKGxtcC0+aW4pOwogICAgICAg ICAgICAgbG1wLT5pbiA9IG5ldzsKKyAgICAgICAgICAgIGZyZWVtdXN0IChybXApOwogICAgICAg ICAgIH0KICAgICAgICAgICBicmVhazsKIAogICAgICAgICBjYXNlIFBMVVM6Ci0gICAgICAgICAg YXNzZXJ0IChtdXN0cyA8IG1wKTsKLSAgICAgICAgICAtLW1wOworICAgICAgICAgIGFzc2VydCAo bXAgIT0gTlVMTCk7CiAgICAgICAgICAgbXAtPmlzWzBdID0gJ1wwJzsKICAgICAgICAgICBicmVh azsKIAogICAgICAgICBjYXNlIEVORDoKLSAgICAgICAgICBhc3NlcnQgKG1wID09ICZtdXN0c1sx XSk7Ci0gICAgICAgICAgZm9yIChpID0gMDsgbXVzdHNbMF0uaW5baV0gIT0gTlVMTDsgKytpKQot ICAgICAgICAgICAgaWYgKHN0cmxlbiAobXVzdHNbMF0uaW5baV0pID4gc3RybGVuIChyZXN1bHQp KQotICAgICAgICAgICAgICByZXN1bHQgPSBtdXN0c1swXS5pbltpXTsKLSAgICAgICAgICBpZiAo U1RSRVEgKHJlc3VsdCwgbXVzdHNbMF0uaXMpKQotICAgICAgICAgICAgZXhhY3QgPSB0cnVlOwor ICAgICAgICAgIGFzc2VydCAoIW1wIHx8ICFtcC0+cHJldik7CisgICAgICAgICAgaWYgKG1wKQor ICAgICAgICAgICAgeworICAgICAgICAgICAgICBmb3IgKGkgPSAwOyBtcC0+aW5baV0gIT0gTlVM TDsgKytpKQorICAgICAgICAgICAgICAgIGlmIChzdHJsZW4gKG1wLT5pbltpXSkgPiBzdHJsZW4g KHJlc3VsdCkpCisgICAgICAgICAgICAgICAgICByZXN1bHQgPSBtcC0+aW5baV07CisgICAgICAg ICAgICAgIGlmIChTVFJFUSAocmVzdWx0LCBtcC0+aXMpKQorICAgICAgICAgICAgICAgIGV4YWN0 ID0gdHJ1ZTsKKyAgICAgICAgICAgIH0KICAgICAgICAgICBnb3RvIGRvbmU7CiAKICAgICAgICAg Y2FzZSBDQVQ6Ci0gICAgICAgICAgYXNzZXJ0ICgmbXVzdHNbMl0gPD0gbXApOworICAgICAgICAg IGFzc2VydCAobXAgJiYgbXAtPnByZXYpOwogICAgICAgICAgIHsKICAgICAgICAgICAgIG11c3Qg KmxtcDsKICAgICAgICAgICAgIG11c3QgKnJtcDsKIAotICAgICAgICAgICAgcm1wID0gLS1tcDsK LSAgICAgICAgICAgIGxtcCA9IC0tbXA7CisgICAgICAgICAgICBybXAgPSBtcDsKKyAgICAgICAg ICAgIGxtcCA9IG1wID0gbXAtPnByZXY7CiAgICAgICAgICAgICAvKiBJbi4gIEV2ZXJ5dGhpbmcg aW4gbGVmdCwgcGx1cyBldmVyeXRoaW5nIGluCiAgICAgICAgICAgICAgICByaWdodCwgcGx1cyBj b25jYXRlbmF0aW9uIG9mCiAgICAgICAgICAgICAgICBsZWZ0J3MgcmlnaHQgYW5kIHJpZ2h0J3Mg bGVmdC4gICovCkBAIC00MTkyLDYgKzQyMDAsNyBAQCBkZmFtdXN0IChzdHJ1Y3QgZGZhICpkKQog ICAgICAgICAgICAgICB9CiAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgIGxtcC0+aXNb MF0gPSAnXDAnOworICAgICAgICAgICAgZnJlZW11c3QgKHJtcCk7CiAgICAgICAgICAgfQogICAg ICAgICAgIGJyZWFrOwogCkBAIC00MjAwLDYgKzQyMDksNyBAQCBkZmFtdXN0IChzdHJ1Y3QgZGZh ICpkKQogICAgICAgICAgIGdvdG8gZG9uZTsKIAogICAgICAgICBkZWZhdWx0OgorICAgICAgICAg IG1wID0gYWxsb2NtdXN0IChtcCk7CiAgICAgICAgICAgcmVzZXRtdXN0IChtcCk7CiAgICAgICAg ICAgaWYgKENTRVQgPD0gdCkKICAgICAgICAgICAgIHsKQEAgLTQyMzEsMTcgKzQyNDEsNiBAQCBk ZmFtdXN0IChzdHJ1Y3QgZGZhICpkKQogICAgICAgICAgICAgZ290byBkb25lOwogICAgICAgICAg IGJyZWFrOwogICAgICAgICB9Ci0jaWZkZWYgREVCVUcKLSAgICAgIGZwcmludGYgKHN0ZGVyciwg IiBub2RlOiAlemQ6IiwgcmkpOwotICAgICAgcHJ0b2sgKGQtPnRva2Vuc1tyaV0pOwotICAgICAg ZnByaW50ZiAoc3RkZXJyLCAiXG4gIGluOiIpOwotICAgICAgZm9yIChpID0gMDsgbXAtPmluW2ld OyArK2kpCi0gICAgICAgIGZwcmludGYgKHN0ZGVyciwgIiBcIiVzXCIiLCBtcC0+aW5baV0pOwot ICAgICAgZnByaW50ZiAoc3RkZXJyLCAiXG4gIGlzOiBcIiVzXCJcbiIsIG1wLT5pcyk7Ci0gICAg ICBmcHJpbnRmIChzdGRlcnIsICIgIGxlZnQ6IFwiJXNcIlxuIiwgbXAtPmxlZnQpOwotICAgICAg ZnByaW50ZiAoc3RkZXJyLCAiICByaWdodDogXCIlc1wiXG4iLCBtcC0+cmlnaHQpOwotI2VuZGlm Ci0gICAgICArK21wOwogICAgIH0KIGRvbmU6CiAgIGlmIChzdHJsZW4gKHJlc3VsdCkpCkBAIC00 MjUyLDE2ICs0MjUxLDggQEAgZG9uZToKICAgICAgIGRtLT5uZXh0ID0gZC0+bXVzdHM7CiAgICAg ICBkLT5tdXN0cyA9IGRtOwogICAgIH0KLSAgbXAgPSBtdXN0czsKLSAgZm9yIChpID0gMDsgaSA8 PSBkLT50aW5kZXg7ICsraSkKLSAgICB7Ci0gICAgICBmcmVlbGlzdCAobXBbaV0uaW4pOwotICAg ICAgZnJlZSAobXBbaV0uaW4pOwotICAgICAgZnJlZSAobXBbaV0ubGVmdCk7Ci0gICAgICBmcmVl IChtcFtpXS5yaWdodCk7Ci0gICAgICBmcmVlIChtcFtpXS5pcyk7Ci0gICAgfQotICBmcmVlICht cCk7CisgIGlmIChtcCkKKyAgICBmcmVlbXVzdCAobXApOwogfQogCiBzdHJ1Y3QgZGZhICoKLS0g CjEuOS4yCgo= --------_5348D690000000002C12_MULTIPART_MIXED_-- From debbugs-submit-bounces@debbugs.gnu.org Fri Apr 18 11:04:34 2014 Received: (at 17248) by debbugs.gnu.org; 18 Apr 2014 15:04:35 +0000 Received: from localhost ([127.0.0.1]:52048 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WbALC-0002jf-6P for submit@debbugs.gnu.org; Fri, 18 Apr 2014 11:04:34 -0400 Received: from mailgw04.kcn.ne.jp ([61.86.7.211]:54613) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WbAL9-0002jU-MT for 17248@debbugs.gnu.org; Fri, 18 Apr 2014 11:04:32 -0400 Received: from imp01 (mailgw5.kcn.ne.jp [61.86.15.231]) by mailgw04.kcn.ne.jp (Postfix) with ESMTP id EC2886C154E for <17248@debbugs.gnu.org>; Sat, 19 Apr 2014 00:04:29 +0900 (JST) Received: from mail07.kcn.ne.jp ([61.86.6.186]) by imp01 with bizsmtp id rT4V1n00y40oyB901T4VrN; Sat, 19 Apr 2014 00:04:29 +0900 X-OrgRCPT: 17248@debbugs.gnu.org Received: from [10.120.1.61] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail07.kcn.ne.jp (Postfix) with ESMTPA id 86D63D500B6 for <17248@debbugs.gnu.org>; Sat, 19 Apr 2014 00:04:29 +0900 (JST) Date: Sat, 19 Apr 2014 00:04:30 +0900 From: Norihiro Tanaka To: 17248@debbugs.gnu.org Subject: bug#17248: [PATCH] grep: waste of a lot of memory for a large pattern in dfamust In-Reply-To: <20140412151001.2C0C.27F6AC2D@kcn.ne.jp> References: <20140412151001.2C0C.27F6AC2D@kcn.ne.jp> Message-Id: <20140419000430.701D.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_53513EBB000000007011_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 17248 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) --------_53513EBB000000007011_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit I rebased this patch because of confliction. --------_53513EBB000000007011_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="patch.txt" Content-Disposition: attachment; filename="patch.txt" Content-Transfer-Encoding: base64 RnJvbSBlMzk3MDE5MzE3MDNjYTdmYzYwM2M1ZTJlMzhmNTgwNzMwYTI0YmUyIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTYXQsIDEyIEFwciAyMDE0IDE0OjIwOjExICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZ3Jl cDogd2FzdGUgb2YgYSBsb3Qgb2YgbWVtb3J5IGZvciBhIGxhcmdlIHBhdHRlcm4gaW4gZGZhbXVz dAoKKiBzcmMvZGZhLmMgKHN0cnVjdCBtdXN0KTogTmV3IG1lbWJlciBgcHJldicuICBJdCBoYXMg dGhlIHBvaW50ZXIgdG8KcHJldmlvdXMgbXVzdC4KKGFsbG9jbXVzdCk6IE5ldyBmdW5jdGlvbi4K KGZyZWVtdXN0KTogTmV3IGZ1bmN0aW9uLgooZGZhbXVzdCk6IFVzZSBpdC4KLS0tCiBzcmMvZGZh LmMgfCAxMTcgKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0KIDEgZmlsZSBjaGFuZ2VkLCA1NyBpbnNlcnRpb25zKCspLCA2MCBkZWxl dGlvbnMoLSkKCmRpZmYgLS1naXQgYS9zcmMvZGZhLmMgYi9zcmMvZGZhLmMKaW5kZXggZWVjYTI1 Ny4uOTY2MWMwYyAxMDA2NDQKLS0tIGEvc3JjL2RmYS5jCisrKyBiL3NyYy9kZmEuYwpAQCAtMzgy MSwxMyArMzgyMSwzMCBAQCBpbmJvdGggKGNoYXIgKipsZWZ0LCBjaGFyICoqcmlnaHQpCiAgIHJl dHVybiBib3RoOwogfQogCi10eXBlZGVmIHN0cnVjdAordHlwZWRlZiBzdHJ1Y3QgbXVzdCBtdXN0 OworCitzdHJ1Y3QgbXVzdAogewogICBjaGFyICoqaW47CiAgIGNoYXIgKmxlZnQ7CiAgIGNoYXIg KnJpZ2h0OwogICBjaGFyICppczsKLX0gbXVzdDsKKyAgbXVzdCAqcHJldjsKK307CisKK3N0YXRp YyBtdXN0ICoKK2FsbG9jbXVzdCAobXVzdCAqcHJldikKK3sKKyAgbXVzdCAqbXAgPSB4bWFsbG9j IChzaXplb2YgKnByZXYpOworICBtcC0+aW4gPSB4bWFsbG9jIChzaXplb2YgKm1wLT5pbik7Cisg IG1wLT5sZWZ0ID0geG1hbGxvYyAoMik7CisgIG1wLT5yaWdodCA9IHhtYWxsb2MgKDIpOworICBt cC0+aXMgPSB4bWFsbG9jICgyKTsKKyAgbXAtPmxlZnRbMF0gPSBtcC0+cmlnaHRbMF0gPSBtcC0+ aXNbMF0gPSAnXDAnOworICBtcC0+aW5bMF0gPSBOVUxMOworICBtcC0+cHJldiA9IHByZXY7Cisg IHJldHVybiBtcDsKK30KIAogc3RhdGljIHZvaWQKIHJlc2V0bXVzdCAobXVzdCAqIG1wKQpAQCAt MzgzOCwzMiArMzg1NSwyNiBAQCByZXNldG11c3QgKG11c3QgKiBtcCkKIH0KIAogc3RhdGljIHZv aWQKK2ZyZWVtdXN0IChtdXN0ICptcCkKK3sKKyAgZnJlZWxpc3QgKG1wLT5pbik7CisgIGZyZWUg KG1wLT5pbik7CisgIGZyZWUgKG1wLT5sZWZ0KTsKKyAgZnJlZSAobXAtPnJpZ2h0KTsKKyAgZnJl ZSAobXAtPmlzKTsKKyAgZnJlZSAobXApOworfQorCitzdGF0aWMgdm9pZAogZGZhbXVzdCAoc3Ry dWN0IGRmYSAqZCkKIHsKLSAgbXVzdCAqbXVzdHMgPSB4bm1hbGxvYyAoZC0+dGluZGV4ICsgMSwg c2l6ZW9mICptdXN0cyk7Ci0gIG11c3QgKm1wID0gbXVzdHM7CisgIG11c3QgKm1wID0gTlVMTDsK ICAgY2hhciBjb25zdCAqcmVzdWx0ID0gIiI7CiAgIHNpemVfdCByaTsKICAgc2l6ZV90IGk7CiAg IGJvb2wgZXhhY3QgPSBmYWxzZTsKICAgc3RydWN0IGRmYW11c3QgKmRtOwogCi0gIGZvciAoaSA9 IDA7IGkgPD0gZC0+dGluZGV4OyArK2kpCi0gICAgewotICAgICAgbXBbaV0uaW4gPSB4emFsbG9j IChzaXplb2YgKm1wW2ldLmluKTsKLSAgICAgIG1wW2ldLmxlZnQgPSB4emFsbG9jICgyKTsKLSAg ICAgIG1wW2ldLnJpZ2h0ID0geHphbGxvYyAoMik7Ci0gICAgICBtcFtpXS5pcyA9IHh6YWxsb2Mg KDIpOwotICAgIH0KLSNpZmRlZiBERUJVRwotICBmcHJpbnRmIChzdGRlcnIsICJkZmFtdXN0Olxu Iik7Ci0gIGZvciAoaSA9IDA7IGkgPCBkLT50aW5kZXg7ICsraSkKLSAgICB7Ci0gICAgICBmcHJp bnRmIChzdGRlcnIsICIgJXpkOiIsIGkpOwotICAgICAgcHJ0b2sgKGQtPnRva2Vuc1tpXSk7Ci0g ICAgfQotICBwdXRjICgnXG4nLCBzdGRlcnIpOwotI2VuZGlmCiAgIGZvciAocmkgPSAwOyByaSA8 IGQtPnRpbmRleDsgKytyaSkKICAgICB7CiAgICAgICB0b2tlbiB0ID0gZC0+dG9rZW5zW3JpXTsK QEAgLTM4NzMsMTEgKzM4ODQsNiBAQCBkZmFtdXN0IChzdHJ1Y3QgZGZhICpkKQogICAgICAgICBj YXNlIFJQQVJFTjoKICAgICAgICAgICBhc3NlcnQgKCEibmVpdGhlciBMUEFSRU4gbm9yIFJQQVJF TiBtYXkgYXBwZWFyIGhlcmUiKTsKIAotICAgICAgICBjYXNlIFNUQVI6Ci0gICAgICAgIGNhc2Ug UU1BUks6Ci0gICAgICAgICAgYXNzZXJ0IChtdXN0cyA8IG1wKTsKLSAgICAgICAgICAtLW1wOwot ICAgICAgICAgIC8qIEZhbGwgdGhyb3VnaC4gICovCiAgICAgICAgIGNhc2UgRU1QVFk6CiAgICAg ICAgIGNhc2UgQkVHTElORToKICAgICAgICAgY2FzZSBFTkRMSU5FOgpAQCAtMzg4OCwxOSArMzg5 NCwyNCBAQCBkZmFtdXN0IChzdHJ1Y3QgZGZhICpkKQogICAgICAgICBjYXNlIEJBQ0tSRUY6CiAg ICAgICAgIGNhc2UgQU5ZQ0hBUjoKICAgICAgICAgY2FzZSBNQkNTRVQ6CisgICAgICAgICAgbXAg PSBhbGxvY211c3QgKG1wKTsKKyAgICAgICAgICAvKiBGYWxsIHRocm91Z2guICAqLworICAgICAg ICBjYXNlIFNUQVI6CisgICAgICAgIGNhc2UgUU1BUks6CisgICAgICAgICAgYXNzZXJ0IChtcCAh PSBOVUxMKTsKICAgICAgICAgICByZXNldG11c3QgKG1wKTsKICAgICAgICAgICBicmVhazsKIAog ICAgICAgICBjYXNlIE9SOgotICAgICAgICAgIGFzc2VydCAoJm11c3RzWzJdIDw9IG1wKTsKKyAg ICAgICAgICBhc3NlcnQgKG1wICYmIG1wLT5wcmV2KTsKICAgICAgICAgICB7CiAgICAgICAgICAg ICBjaGFyICoqbmV3OwogICAgICAgICAgICAgbXVzdCAqbG1wOwogICAgICAgICAgICAgbXVzdCAq cm1wOwogICAgICAgICAgICAgc2l6ZV90IGosIGxuLCBybiwgbjsKIAotICAgICAgICAgICAgcm1w ID0gLS1tcDsKLSAgICAgICAgICAgIGxtcCA9IC0tbXA7CisgICAgICAgICAgICBybXAgPSBtcDsK KyAgICAgICAgICAgIGxtcCA9IG1wID0gbXAtPnByZXY7CiAgICAgICAgICAgICAvKiBHdWFyYW50 ZWVkIHRvIGJlLiAgVW5saWtlbHksIGJ1dCAuLi4gICovCiAgICAgICAgICAgICBpZiAoIVNUUkVR IChsbXAtPmlzLCBybXAtPmlzKSkKICAgICAgICAgICAgICAgbG1wLT5pc1swXSA9ICdcMCc7CkBA IC0zOTI1LDMyICszOTM2LDM1IEBAIGRmYW11c3QgKHN0cnVjdCBkZmEgKmQpCiAgICAgICAgICAg ICBmcmVlbGlzdCAobG1wLT5pbik7CiAgICAgICAgICAgICBmcmVlIChsbXAtPmluKTsKICAgICAg ICAgICAgIGxtcC0+aW4gPSBuZXc7CisgICAgICAgICAgICBmcmVlbXVzdCAocm1wKTsKICAgICAg ICAgICB9CiAgICAgICAgICAgYnJlYWs7CiAKICAgICAgICAgY2FzZSBQTFVTOgotICAgICAgICAg IGFzc2VydCAobXVzdHMgPCBtcCk7Ci0gICAgICAgICAgLS1tcDsKKyAgICAgICAgICBhc3NlcnQg KG1wICE9IE5VTEwpOwogICAgICAgICAgIG1wLT5pc1swXSA9ICdcMCc7CiAgICAgICAgICAgYnJl YWs7CiAKICAgICAgICAgY2FzZSBFTkQ6Ci0gICAgICAgICAgYXNzZXJ0IChtcCA9PSAmbXVzdHNb MV0pOwotICAgICAgICAgIGZvciAoaSA9IDA7IG11c3RzWzBdLmluW2ldICE9IE5VTEw7ICsraSkK LSAgICAgICAgICAgIGlmIChzdHJsZW4gKG11c3RzWzBdLmluW2ldKSA+IHN0cmxlbiAocmVzdWx0 KSkKLSAgICAgICAgICAgICAgcmVzdWx0ID0gbXVzdHNbMF0uaW5baV07Ci0gICAgICAgICAgaWYg KFNUUkVRIChyZXN1bHQsIG11c3RzWzBdLmlzKSkKLSAgICAgICAgICAgIGV4YWN0ID0gdHJ1ZTsK KyAgICAgICAgICBhc3NlcnQgKCFtcCB8fCAhbXAtPnByZXYpOworICAgICAgICAgIGlmIChtcCkK KyAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgZm9yIChpID0gMDsgbXAtPmluW2ldICE9IE5V TEw7ICsraSkKKyAgICAgICAgICAgICAgICBpZiAoc3RybGVuIChtcC0+aW5baV0pID4gc3RybGVu IChyZXN1bHQpKQorICAgICAgICAgICAgICAgICAgcmVzdWx0ID0gbXAtPmluW2ldOworICAgICAg ICAgICAgICBpZiAoU1RSRVEgKHJlc3VsdCwgbXAtPmlzKSkKKyAgICAgICAgICAgICAgICBleGFj dCA9IHRydWU7CisgICAgICAgICAgICB9CiAgICAgICAgICAgZ290byBkb25lOwogCiAgICAgICAg IGNhc2UgQ0FUOgotICAgICAgICAgIGFzc2VydCAoJm11c3RzWzJdIDw9IG1wKTsKKyAgICAgICAg ICBhc3NlcnQgKG1wICYmIG1wLT5wcmV2KTsKICAgICAgICAgICB7CiAgICAgICAgICAgICBtdXN0 ICpsbXA7CiAgICAgICAgICAgICBtdXN0ICpybXA7CiAKLSAgICAgICAgICAgIHJtcCA9IC0tbXA7 Ci0gICAgICAgICAgICBsbXAgPSAtLW1wOworICAgICAgICAgICAgcm1wID0gbXA7CisgICAgICAg ICAgICBsbXAgPSBtcCA9IG1wLT5wcmV2OwogICAgICAgICAgICAgLyogSW4uICBFdmVyeXRoaW5n IGluIGxlZnQsIHBsdXMgZXZlcnl0aGluZyBpbgogICAgICAgICAgICAgICAgcmlnaHQsIHBsdXMg Y29uY2F0ZW5hdGlvbiBvZgogICAgICAgICAgICAgICAgbGVmdCdzIHJpZ2h0IGFuZCByaWdodCdz IGxlZnQuICAqLwpAQCAtMzk3Nyw2ICszOTkxLDcgQEAgZGZhbXVzdCAoc3RydWN0IGRmYSAqZCkK ICAgICAgICAgICAgICAgbG1wLT5pcyA9IGljYXRhbGxvYyAobG1wLT5pcywgcm1wLT5pcyk7CiAg ICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgIGxtcC0+aXNbMF0gPSAnXDAnOworICAgICAg ICAgICAgZnJlZW11c3QgKHJtcCk7CiAgICAgICAgICAgfQogICAgICAgICAgIGJyZWFrOwogCkBA IC0zOTg1LDYgKzQwMDAsNyBAQCBkZmFtdXN0IChzdHJ1Y3QgZGZhICpkKQogICAgICAgICAgIGdv dG8gZG9uZTsKIAogICAgICAgICBkZWZhdWx0OgorICAgICAgICAgIG1wID0gYWxsb2NtdXN0ICht cCk7CiAgICAgICAgICAgcmVzZXRtdXN0IChtcCk7CiAgICAgICAgICAgaWYgKENTRVQgPD0gdCkK ICAgICAgICAgICAgIHsKQEAgLTQwMTQsMTcgKzQwMzAsNiBAQCBkZmFtdXN0IChzdHJ1Y3QgZGZh ICpkKQogICAgICAgICAgIG1wLT5pbiA9IGVubGlzdCAobXAtPmluLCBtcC0+aXMsIDEpOwogICAg ICAgICAgIGJyZWFrOwogICAgICAgICB9Ci0jaWZkZWYgREVCVUcKLSAgICAgIGZwcmludGYgKHN0 ZGVyciwgIiBub2RlOiAlemQ6IiwgcmkpOwotICAgICAgcHJ0b2sgKGQtPnRva2Vuc1tyaV0pOwot ICAgICAgZnByaW50ZiAoc3RkZXJyLCAiXG4gIGluOiIpOwotICAgICAgZm9yIChpID0gMDsgbXAt PmluW2ldOyArK2kpCi0gICAgICAgIGZwcmludGYgKHN0ZGVyciwgIiBcIiVzXCIiLCBtcC0+aW5b aV0pOwotICAgICAgZnByaW50ZiAoc3RkZXJyLCAiXG4gIGlzOiBcIiVzXCJcbiIsIG1wLT5pcyk7 Ci0gICAgICBmcHJpbnRmIChzdGRlcnIsICIgIGxlZnQ6IFwiJXNcIlxuIiwgbXAtPmxlZnQpOwot ICAgICAgZnByaW50ZiAoc3RkZXJyLCAiICByaWdodDogXCIlc1wiXG4iLCBtcC0+cmlnaHQpOwot I2VuZGlmCi0gICAgICArK21wOwogICAgIH0KIGRvbmU6CiAgIGlmICgqcmVzdWx0KQpAQCAtNDAz NSwxNiArNDA0MCw4IEBAIGRvbmU6CiAgICAgICBkbS0+bmV4dCA9IGQtPm11c3RzOwogICAgICAg ZC0+bXVzdHMgPSBkbTsKICAgICB9Ci0gIG1wID0gbXVzdHM7Ci0gIGZvciAoaSA9IDA7IGkgPD0g ZC0+dGluZGV4OyArK2kpCi0gICAgewotICAgICAgZnJlZWxpc3QgKG1wW2ldLmluKTsKLSAgICAg IGZyZWUgKG1wW2ldLmluKTsKLSAgICAgIGZyZWUgKG1wW2ldLmxlZnQpOwotICAgICAgZnJlZSAo bXBbaV0ucmlnaHQpOwotICAgICAgZnJlZSAobXBbaV0uaXMpOwotICAgIH0KLSAgZnJlZSAobXAp OworICBpZiAobXApCisgICAgZnJlZW11c3QgKG1wKTsKIH0KIAogc3RydWN0IGRmYSAqCi0tIAox LjkuMgoK --------_53513EBB000000007011_MULTIPART_MIXED_-- From debbugs-submit-bounces@debbugs.gnu.org Sat Apr 19 20:59:28 2014 Received: (at 17248) by debbugs.gnu.org; 20 Apr 2014 00:59:28 +0000 Received: from localhost ([127.0.0.1]:52899 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wbg6R-0002EI-Bc for submit@debbugs.gnu.org; Sat, 19 Apr 2014 20:59:27 -0400 Received: from mailgw06.kcn.ne.jp ([61.86.7.213]:54200) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wbg6O-0002E4-5k for 17248@debbugs.gnu.org; Sat, 19 Apr 2014 20:59:25 -0400 Received: from imp03 (mailgw7.kcn.ne.jp [61.86.15.238]) by mailgw06.kcn.ne.jp (Postfix) with ESMTP id 40D9EE88002 for <17248@debbugs.gnu.org>; Sun, 20 Apr 2014 09:59:23 +0900 (JST) Received: from mail08.kcn.ne.jp ([61.86.6.187]) by imp03 with bizsmtp id s0zP1n008426eXR010zPGz; Sun, 20 Apr 2014 09:59:23 +0900 X-OrgRCPT: 17248@debbugs.gnu.org Received: from [10.120.1.58] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail08.kcn.ne.jp (Postfix) with ESMTPA id 0E42012B802E for <17248@debbugs.gnu.org>; Sun, 20 Apr 2014 09:59:23 +0900 (JST) Date: Sun, 20 Apr 2014 09:59:24 +0900 From: Norihiro Tanaka To: 17248@debbugs.gnu.org Subject: bug#17248: [PATCH] grep: waste of a lot of memory for a large pattern in dfamust In-Reply-To: <20140419000430.701D.27F6AC2D@kcn.ne.jp> References: <20140412151001.2C0C.27F6AC2D@kcn.ne.jp> <20140419000430.701D.27F6AC2D@kcn.ne.jp> Message-Id: <20140420095921.8FFD.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_53531B9E000000008FE9_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 17248 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) --------_53531B9E000000008FE9_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Norihiro Tanaka wrote: > I rebased this patch because of confliction. I fixed the degration in rebase. --------_53531B9E000000008FE9_MULTIPART_MIXED_ Content-Type: text/plain; charset="UTF-8"; name="patch.txt" Content-Disposition: attachment; filename="patch.txt" Content-Transfer-Encoding: base64 RnJvbSBmMDQ2NDQ5ZjJlZTI5YWRiOWFiNzM0MDJkYzcyZWFlOGZmM2Q2ZjBiIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTYXQsIDEyIEFwciAyMDE0IDE0OjIwOjExICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZ3Jl cDogd2FzdGUgb2YgYSBsb3Qgb2YgbWVtb3J5IGZvciBhIGxhcmdlIHBhdHRlcm4gaW4gZGZhbXVz dAoKKiBzcmMvZGZhLmMgKHN0cnVjdCBtdXN0KTogTmV3IG1lbWJlciBgcHJldicuICBJdCBoYXMg dGhlIHBvaW50ZXIgdG8KcHJldmlvdXMgbXVzdC4KKGFsbG9jbXVzdCk6IE5ldyBmdW5jdGlvbi4K KGZyZWVtdXN0KTogTmV3IGZ1bmN0aW9uLgooZGZhbXVzdCk6IFVzZSBpdC4KLS0tCiBzcmMvZGZh LmMgfCAxMTUgKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0KIDEgZmlsZSBjaGFuZ2VkLCA1NSBpbnNlcnRpb25zKCspLCA2MCBkZWxl dGlvbnMoLSkKCmRpZmYgLS1naXQgYS9zcmMvZGZhLmMgYi9zcmMvZGZhLmMKaW5kZXggOTBjZjRh OS4uMTY1OGVjOSAxMDA2NDQKLS0tIGEvc3JjL2RmYS5jCisrKyBiL3NyYy9kZmEuYwpAQCAtMzgy MSwxMyArMzgyMSwyOCBAQCBpbmJvdGggKGNoYXIgKipsZWZ0LCBjaGFyICoqcmlnaHQpCiAgIHJl dHVybiBib3RoOwogfQogCi10eXBlZGVmIHN0cnVjdAordHlwZWRlZiBzdHJ1Y3QgbXVzdCBtdXN0 OworCitzdHJ1Y3QgbXVzdAogewogICBjaGFyICoqaW47CiAgIGNoYXIgKmxlZnQ7CiAgIGNoYXIg KnJpZ2h0OwogICBjaGFyICppczsKLX0gbXVzdDsKKyAgbXVzdCAqcHJldjsKK307CisKK3N0YXRp YyBtdXN0ICoKK2FsbG9jbXVzdCAobXVzdCAqcHJldikKK3sKKyAgbXVzdCAqbXAgPSB4emFsbG9j IChzaXplb2YgKnByZXYpOworICBtcC0+aW4gPSB4emFsbG9jIChzaXplb2YgKm1wLT5pbik7Cisg IG1wLT5sZWZ0ID0geHphbGxvYyAoMik7CisgIG1wLT5yaWdodCA9IHh6YWxsb2MgKDIpOworICBt cC0+aXMgPSB4emFsbG9jICgyKTsKKyAgbXAtPnByZXYgPSBwcmV2OworICByZXR1cm4gbXA7Cit9 CiAKIHN0YXRpYyB2b2lkCiByZXNldG11c3QgKG11c3QgKiBtcCkKQEAgLTM4MzgsMzIgKzM4NTMs MjYgQEAgcmVzZXRtdXN0IChtdXN0ICogbXApCiB9CiAKIHN0YXRpYyB2b2lkCitmcmVlbXVzdCAo bXVzdCAqbXApCit7CisgIGZyZWVsaXN0IChtcC0+aW4pOworICBmcmVlIChtcC0+aW4pOworICBm cmVlIChtcC0+bGVmdCk7CisgIGZyZWUgKG1wLT5yaWdodCk7CisgIGZyZWUgKG1wLT5pcyk7Cisg IGZyZWUgKG1wKTsKK30KKworc3RhdGljIHZvaWQKIGRmYW11c3QgKHN0cnVjdCBkZmEgKmQpCiB7 Ci0gIG11c3QgKm11c3RzID0geG5tYWxsb2MgKGQtPnRpbmRleCArIDEsIHNpemVvZiAqbXVzdHMp OwotICBtdXN0ICptcCA9IG11c3RzOworICBtdXN0ICptcCA9IE5VTEw7CiAgIGNoYXIgY29uc3Qg KnJlc3VsdCA9ICIiOwogICBzaXplX3Qgcmk7CiAgIHNpemVfdCBpOwogICBib29sIGV4YWN0ID0g ZmFsc2U7CiAgIHN0cnVjdCBkZmFtdXN0ICpkbTsKIAotICBmb3IgKGkgPSAwOyBpIDw9IGQtPnRp bmRleDsgKytpKQotICAgIHsKLSAgICAgIG1wW2ldLmluID0geHphbGxvYyAoc2l6ZW9mICptcFtp XS5pbik7Ci0gICAgICBtcFtpXS5sZWZ0ID0geHphbGxvYyAoMik7Ci0gICAgICBtcFtpXS5yaWdo dCA9IHh6YWxsb2MgKDIpOwotICAgICAgbXBbaV0uaXMgPSB4emFsbG9jICgyKTsKLSAgICB9Ci0j aWZkZWYgREVCVUcKLSAgZnByaW50ZiAoc3RkZXJyLCAiZGZhbXVzdDpcbiIpOwotICBmb3IgKGkg PSAwOyBpIDwgZC0+dGluZGV4OyArK2kpCi0gICAgewotICAgICAgZnByaW50ZiAoc3RkZXJyLCAi ICV6ZDoiLCBpKTsKLSAgICAgIHBydG9rIChkLT50b2tlbnNbaV0pOwotICAgIH0KLSAgcHV0YyAo J1xuJywgc3RkZXJyKTsKLSNlbmRpZgogICBmb3IgKHJpID0gMDsgcmkgPCBkLT50aW5kZXg7ICsr cmkpCiAgICAgewogICAgICAgdG9rZW4gdCA9IGQtPnRva2Vuc1tyaV07CkBAIC0zODczLDExICsz ODgyLDYgQEAgZGZhbXVzdCAoc3RydWN0IGRmYSAqZCkKICAgICAgICAgY2FzZSBSUEFSRU46CiAg ICAgICAgICAgYXNzZXJ0ICghIm5laXRoZXIgTFBBUkVOIG5vciBSUEFSRU4gbWF5IGFwcGVhciBo ZXJlIik7CiAKLSAgICAgICAgY2FzZSBTVEFSOgotICAgICAgICBjYXNlIFFNQVJLOgotICAgICAg ICAgIGFzc2VydCAobXVzdHMgPCBtcCk7Ci0gICAgICAgICAgLS1tcDsKLSAgICAgICAgICAvKiBG YWxsIHRocm91Z2guICAqLwogICAgICAgICBjYXNlIEVNUFRZOgogICAgICAgICBjYXNlIEJFR0xJ TkU6CiAgICAgICAgIGNhc2UgRU5ETElORToKQEAgLTM4ODgsMTkgKzM4OTIsMjQgQEAgZGZhbXVz dCAoc3RydWN0IGRmYSAqZCkKICAgICAgICAgY2FzZSBCQUNLUkVGOgogICAgICAgICBjYXNlIEFO WUNIQVI6CiAgICAgICAgIGNhc2UgTUJDU0VUOgorICAgICAgICAgIG1wID0gYWxsb2NtdXN0ICht cCk7CisgICAgICAgICAgLyogRmFsbCB0aHJvdWdoLiAgKi8KKyAgICAgICAgY2FzZSBTVEFSOgor ICAgICAgICBjYXNlIFFNQVJLOgorICAgICAgICAgIGFzc2VydCAobXAgIT0gTlVMTCk7CiAgICAg ICAgICAgcmVzZXRtdXN0IChtcCk7CiAgICAgICAgICAgYnJlYWs7CiAKICAgICAgICAgY2FzZSBP UjoKLSAgICAgICAgICBhc3NlcnQgKCZtdXN0c1syXSA8PSBtcCk7CisgICAgICAgICAgYXNzZXJ0 IChtcCAmJiBtcC0+cHJldik7CiAgICAgICAgICAgewogICAgICAgICAgICAgY2hhciAqKm5ldzsK ICAgICAgICAgICAgIG11c3QgKmxtcDsKICAgICAgICAgICAgIG11c3QgKnJtcDsKICAgICAgICAg ICAgIHNpemVfdCBqLCBsbiwgcm4sIG47CiAKLSAgICAgICAgICAgIHJtcCA9IC0tbXA7Ci0gICAg ICAgICAgICBsbXAgPSAtLW1wOworICAgICAgICAgICAgcm1wID0gbXA7CisgICAgICAgICAgICBs bXAgPSBtcCA9IG1wLT5wcmV2OwogICAgICAgICAgICAgLyogR3VhcmFudGVlZCB0byBiZS4gIFVu bGlrZWx5LCBidXQgLi4uICAqLwogICAgICAgICAgICAgaWYgKCFTVFJFUSAobG1wLT5pcywgcm1w LT5pcykpCiAgICAgICAgICAgICAgIGxtcC0+aXNbMF0gPSAnXDAnOwpAQCAtMzkyNSwzMiArMzkz NCwzNSBAQCBkZmFtdXN0IChzdHJ1Y3QgZGZhICpkKQogICAgICAgICAgICAgZnJlZWxpc3QgKGxt cC0+aW4pOwogICAgICAgICAgICAgZnJlZSAobG1wLT5pbik7CiAgICAgICAgICAgICBsbXAtPmlu ID0gbmV3OworICAgICAgICAgICAgZnJlZW11c3QgKHJtcCk7CiAgICAgICAgICAgfQogICAgICAg ICAgIGJyZWFrOwogCiAgICAgICAgIGNhc2UgUExVUzoKLSAgICAgICAgICBhc3NlcnQgKG11c3Rz IDwgbXApOwotICAgICAgICAgIC0tbXA7CisgICAgICAgICAgYXNzZXJ0IChtcCAhPSBOVUxMKTsK ICAgICAgICAgICBtcC0+aXNbMF0gPSAnXDAnOwogICAgICAgICAgIGJyZWFrOwogCiAgICAgICAg IGNhc2UgRU5EOgotICAgICAgICAgIGFzc2VydCAobXAgPT0gJm11c3RzWzFdKTsKLSAgICAgICAg ICBmb3IgKGkgPSAwOyBtdXN0c1swXS5pbltpXSAhPSBOVUxMOyArK2kpCi0gICAgICAgICAgICBp ZiAoc3RybGVuIChtdXN0c1swXS5pbltpXSkgPiBzdHJsZW4gKHJlc3VsdCkpCi0gICAgICAgICAg ICAgIHJlc3VsdCA9IG11c3RzWzBdLmluW2ldOwotICAgICAgICAgIGlmIChTVFJFUSAocmVzdWx0 LCBtdXN0c1swXS5pcykpCi0gICAgICAgICAgICBleGFjdCA9IHRydWU7CisgICAgICAgICAgYXNz ZXJ0ICghbXAgfHwgIW1wLT5wcmV2KTsKKyAgICAgICAgICBpZiAobXApCisgICAgICAgICAgICB7 CisgICAgICAgICAgICAgIGZvciAoaSA9IDA7IG1wLT5pbltpXSAhPSBOVUxMOyArK2kpCisgICAg ICAgICAgICAgICAgaWYgKHN0cmxlbiAobXAtPmluW2ldKSA+IHN0cmxlbiAocmVzdWx0KSkKKyAg ICAgICAgICAgICAgICAgIHJlc3VsdCA9IG1wLT5pbltpXTsKKyAgICAgICAgICAgICAgaWYgKFNU UkVRIChyZXN1bHQsIG1wLT5pcykpCisgICAgICAgICAgICAgICAgZXhhY3QgPSB0cnVlOworICAg ICAgICAgICAgfQogICAgICAgICAgIGdvdG8gZG9uZTsKIAogICAgICAgICBjYXNlIENBVDoKLSAg ICAgICAgICBhc3NlcnQgKCZtdXN0c1syXSA8PSBtcCk7CisgICAgICAgICAgYXNzZXJ0IChtcCAm JiBtcC0+cHJldik7CiAgICAgICAgICAgewogICAgICAgICAgICAgbXVzdCAqbG1wOwogICAgICAg ICAgICAgbXVzdCAqcm1wOwogCi0gICAgICAgICAgICBybXAgPSAtLW1wOwotICAgICAgICAgICAg bG1wID0gLS1tcDsKKyAgICAgICAgICAgIHJtcCA9IG1wOworICAgICAgICAgICAgbG1wID0gbXAg PSBtcC0+cHJldjsKICAgICAgICAgICAgIC8qIEluLiAgRXZlcnl0aGluZyBpbiBsZWZ0LCBwbHVz IGV2ZXJ5dGhpbmcgaW4KICAgICAgICAgICAgICAgIHJpZ2h0LCBwbHVzIGNvbmNhdGVuYXRpb24g b2YKICAgICAgICAgICAgICAgIGxlZnQncyByaWdodCBhbmQgcmlnaHQncyBsZWZ0LiAgKi8KQEAg LTM5NzcsNiArMzk4OSw3IEBAIGRmYW11c3QgKHN0cnVjdCBkZmEgKmQpCiAgICAgICAgICAgICAg IGxtcC0+aXMgPSBpY2F0YWxsb2MgKGxtcC0+aXMsIHJtcC0+aXMpOwogICAgICAgICAgICAgZWxz ZQogICAgICAgICAgICAgICBsbXAtPmlzWzBdID0gJ1wwJzsKKyAgICAgICAgICAgIGZyZWVtdXN0 IChybXApOwogICAgICAgICAgIH0KICAgICAgICAgICBicmVhazsKIApAQCAtMzk4NSw2ICszOTk4 LDcgQEAgZGZhbXVzdCAoc3RydWN0IGRmYSAqZCkKICAgICAgICAgICBnb3RvIGRvbmU7CiAKICAg ICAgICAgZGVmYXVsdDoKKyAgICAgICAgICBtcCA9IGFsbG9jbXVzdCAobXApOwogICAgICAgICAg IHJlc2V0bXVzdCAobXApOwogICAgICAgICAgIGlmIChDU0VUIDw9IHQpCiAgICAgICAgICAgICB7 CkBAIC00MDE0LDE3ICs0MDI4LDYgQEAgZGZhbXVzdCAoc3RydWN0IGRmYSAqZCkKICAgICAgICAg ICBtcC0+aW4gPSBlbmxpc3QgKG1wLT5pbiwgbXAtPmlzLCAxKTsKICAgICAgICAgICBicmVhazsK ICAgICAgICAgfQotI2lmZGVmIERFQlVHCi0gICAgICBmcHJpbnRmIChzdGRlcnIsICIgbm9kZTog JXpkOiIsIHJpKTsKLSAgICAgIHBydG9rIChkLT50b2tlbnNbcmldKTsKLSAgICAgIGZwcmludGYg KHN0ZGVyciwgIlxuICBpbjoiKTsKLSAgICAgIGZvciAoaSA9IDA7IG1wLT5pbltpXTsgKytpKQot ICAgICAgICBmcHJpbnRmIChzdGRlcnIsICIgXCIlc1wiIiwgbXAtPmluW2ldKTsKLSAgICAgIGZw cmludGYgKHN0ZGVyciwgIlxuICBpczogXCIlc1wiXG4iLCBtcC0+aXMpOwotICAgICAgZnByaW50 ZiAoc3RkZXJyLCAiICBsZWZ0OiBcIiVzXCJcbiIsIG1wLT5sZWZ0KTsKLSAgICAgIGZwcmludGYg KHN0ZGVyciwgIiAgcmlnaHQ6IFwiJXNcIlxuIiwgbXAtPnJpZ2h0KTsKLSNlbmRpZgotICAgICAg KyttcDsKICAgICB9CiBkb25lOgogICBpZiAoKnJlc3VsdCkKQEAgLTQwMzUsMTYgKzQwMzgsOCBA QCBkb25lOgogICAgICAgZG0tPm5leHQgPSBkLT5tdXN0czsKICAgICAgIGQtPm11c3RzID0gZG07 CiAgICAgfQotICBtcCA9IG11c3RzOwotICBmb3IgKGkgPSAwOyBpIDw9IGQtPnRpbmRleDsgKytp KQotICAgIHsKLSAgICAgIGZyZWVsaXN0IChtcFtpXS5pbik7Ci0gICAgICBmcmVlIChtcFtpXS5p bik7Ci0gICAgICBmcmVlIChtcFtpXS5sZWZ0KTsKLSAgICAgIGZyZWUgKG1wW2ldLnJpZ2h0KTsK LSAgICAgIGZyZWUgKG1wW2ldLmlzKTsKLSAgICB9Ci0gIGZyZWUgKG1wKTsKKyAgaWYgKG1wKQor ICAgIGZyZWVtdXN0IChtcCk7CiB9CiAKIHN0cnVjdCBkZmEgKgotLSAKMS45LjIKCg== --------_53531B9E000000008FE9_MULTIPART_MIXED_-- From debbugs-submit-bounces@debbugs.gnu.org Mon Apr 21 19:09:05 2014 Received: (at 17248) by debbugs.gnu.org; 21 Apr 2014 23:09:05 +0000 Received: from localhost ([127.0.0.1]:54464 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WcNKi-0007jj-3D for submit@debbugs.gnu.org; Mon, 21 Apr 2014 19:09:04 -0400 Received: from mailgw05.kcn.ne.jp ([61.86.7.212]:49423) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WcNKc-0007j9-Nu for 17248@debbugs.gnu.org; Mon, 21 Apr 2014 19:09:00 -0400 Received: from imp03 (mailgw7.kcn.ne.jp [61.86.15.238]) by mailgw05.kcn.ne.jp (Postfix) with ESMTP id CD15267A77 for <17248@debbugs.gnu.org>; Tue, 22 Apr 2014 08:08:56 +0900 (JST) Received: from mail02.kcn.ne.jp ([61.86.6.181]) by imp03 with bizsmtp id sn8w1n00o3uLcVp01n8woo; Tue, 22 Apr 2014 08:08:56 +0900 X-OrgRCPT: 17248@debbugs.gnu.org Received: from [10.120.1.32] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail02.kcn.ne.jp (Postfix) with ESMTPA id 97DB9F10025 for <17248@debbugs.gnu.org>; Tue, 22 Apr 2014 08:08:56 +0900 (JST) Date: Tue, 22 Apr 2014 08:08:57 +0900 From: Norihiro Tanaka To: 17248@debbugs.gnu.org Subject: bug#17248: [PATCH] grep: waste of a lot of memory for a large pattern in dfamust In-Reply-To: <20140419000430.701D.27F6AC2D@kcn.ne.jp> References: <20140412151001.2C0C.27F6AC2D@kcn.ne.jp> <20140419000430.701D.27F6AC2D@kcn.ne.jp> Message-Id: <20140422080839.9492.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5355A2AA00000000948D_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 17248 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) --------_5355A2AA00000000948D_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit I rebased this patch because of confliction again. --------_5355A2AA00000000948D_MULTIPART_MIXED_ Content-Type: text/plain; charset="UTF-8"; name="patch.txt" Content-Disposition: attachment; filename="patch.txt" Content-Transfer-Encoding: base64 RnJvbSAxNGY0ZmU5YmU1YzIyNjdmMDVkMGQ4YTc5YWZlNWNmZDMwODNiMTg5IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTYXQsIDEyIEFwciAyMDE0IDE0OjIwOjExICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZ3Jl cDogd2FzdGUgb2YgYSBsb3Qgb2YgbWVtb3J5IGZvciBhIGxhcmdlIHBhdHRlcm4gaW4gZGZhbXVz dAoKKiBzcmMvZGZhLmMgKHN0cnVjdCBtdXN0KTogTmV3IG1lbWJlciBgcHJldicuICBJdCBoYXMg dGhlIHBvaW50ZXIgdG8KcHJldmlvdXMgbXVzdC4KKGFsbG9jbXVzdCk6IE5ldyBmdW5jdGlvbi4K KGZyZWVtdXN0KTogTmV3IGZ1bmN0aW9uLgooZGZhbXVzdCk6IFVzZSBpdC4KLS0tCiBzcmMvZGZh LmMgfCAxMjcgKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0KIDEgZmlsZSBjaGFuZ2VkLCA2MiBpbnNlcnRpb25zKCspLCA2NSBkZWxl dGlvbnMoLSkKCmRpZmYgLS1naXQgYS9zcmMvZGZhLmMgYi9zcmMvZGZhLmMKaW5kZXggNjVmYzAz ZC4uMjRhN2Q0NCAxMDA2NDQKLS0tIGEvc3JjL2RmYS5jCisrKyBiL3NyYy9kZmEuYwpAQCAtMzgy MSw3ICszODIxLDkgQEAgaW5ib3RoIChjaGFyICoqbGVmdCwgY2hhciAqKnJpZ2h0KQogICByZXR1 cm4gYm90aDsKIH0KIAotdHlwZWRlZiBzdHJ1Y3QKK3R5cGVkZWYgc3RydWN0IG11c3QgbXVzdDsK Kworc3RydWN0IG11c3QKIHsKICAgY2hhciAqKmluOwogICBjaGFyICpsZWZ0OwpAQCAtMzgyOSwy MSArMzgzMSw0NiBAQCB0eXBlZGVmIHN0cnVjdAogICBjaGFyICppczsKICAgYm9vbCBiZWdsaW5l OwogICBib29sIGVuZGxpbmU7Ci19IG11c3Q7CisgIG11c3QgKnByZXY7Cit9OworCitzdGF0aWMg bXVzdCAqCithbGxvY211c3QgKG11c3QgKm1wKQoreworICBtdXN0ICpuZXdfbXAgPSB4emFsbG9j IChzaXplb2YgKm5ld19tcCk7CisgIG5ld19tcC0+aW4gPSB4emFsbG9jIChzaXplb2YgKm5ld19t cC0+aW4pOworICBuZXdfbXAtPmxlZnQgPSB4emFsbG9jICgyKTsKKyAgbmV3X21wLT5yaWdodCA9 IHh6YWxsb2MgKDIpOworICBuZXdfbXAtPmlzID0geHphbGxvYyAoMik7CisgIG5ld19tcC0+cHJl diA9IG1wOworICByZXR1cm4gbmV3X21wOworfQogCiBzdGF0aWMgdm9pZAotcmVzZXRtdXN0ICht dXN0ICogbXApCityZXNldG11c3QgKG11c3QgKm1wKQogewogICBmcmVlbGlzdCAobXAtPmluKTsK ICAgbXAtPmluWzBdID0gTlVMTDsKICAgbXAtPmxlZnRbMF0gPSBtcC0+cmlnaHRbMF0gPSBtcC0+ aXNbMF0gPSAnXDAnOworICBtcC0+YmVnbGluZSA9IGZhbHNlOworICBtcC0+ZW5kbGluZSA9IGZh bHNlOworfQorCitzdGF0aWMgdm9pZAorZnJlZW11c3QgKG11c3QgKm1wKQoreworICBmcmVlbGlz dCAobXAtPmluKTsKKyAgZnJlZSAobXAtPmluKTsKKyAgZnJlZSAobXAtPmxlZnQpOworICBmcmVl IChtcC0+cmlnaHQpOworICBmcmVlIChtcC0+aXMpOworICBmcmVlIChtcCk7CiB9CiAKIHN0YXRp YyB2b2lkCiBkZmFtdXN0IChzdHJ1Y3QgZGZhICpkKQogewotICBtdXN0ICptdXN0cyA9IHhubWFs bG9jIChkLT50aW5kZXggKyAxLCBzaXplb2YgKm11c3RzKTsKLSAgbXVzdCAqbXAgPSBtdXN0czsK KyAgbXVzdCAqbXAgPSBOVUxMOwogICBjaGFyIGNvbnN0ICpyZXN1bHQgPSAiIjsKICAgc2l6ZV90 IHJpOwogICBzaXplX3QgaTsKQEAgLTM4NTIsMzQgKzM4NzksMTggQEAgZGZhbXVzdCAoc3RydWN0 IGRmYSAqZCkKICAgYm9vbCBlbmRsaW5lID0gZmFsc2U7CiAgIHN0cnVjdCBkZmFtdXN0ICpkbTsK IAotICBmb3IgKGkgPSAwOyBpIDw9IGQtPnRpbmRleDsgKytpKQotICAgIHsKLSAgICAgIG1wW2ld LmluID0geHphbGxvYyAoc2l6ZW9mICptcFtpXS5pbik7Ci0gICAgICBtcFtpXS5sZWZ0ID0geHph bGxvYyAoMik7Ci0gICAgICBtcFtpXS5yaWdodCA9IHh6YWxsb2MgKDIpOwotICAgICAgbXBbaV0u aXMgPSB4emFsbG9jICgyKTsKLSAgICAgIG1wW2ldLmJlZ2xpbmUgPSBmYWxzZTsKLSAgICAgIG1w W2ldLmVuZGxpbmUgPSBmYWxzZTsKLSAgICB9Ci0jaWZkZWYgREVCVUcKLSAgZnByaW50ZiAoc3Rk ZXJyLCAiZGZhbXVzdDpcbiIpOwotICBmb3IgKGkgPSAwOyBpIDwgZC0+dGluZGV4OyArK2kpCi0g ICAgewotICAgICAgZnByaW50ZiAoc3RkZXJyLCAiICV6ZDoiLCBpKTsKLSAgICAgIHBydG9rIChk LT50b2tlbnNbaV0pOwotICAgIH0KLSAgcHV0YyAoJ1xuJywgc3RkZXJyKTsKLSNlbmRpZgogICBm b3IgKHJpID0gMDsgcmkgPCBkLT50aW5kZXg7ICsrcmkpCiAgICAgewogICAgICAgdG9rZW4gdCA9 IGQtPnRva2Vuc1tyaV07CiAgICAgICBzd2l0Y2ggKHQpCiAgICAgICAgIHsKICAgICAgICAgY2Fz ZSBCRUdMSU5FOgorICAgICAgICAgIG1wID0gYWxsb2NtdXN0IChtcCk7CiAgICAgICAgICAgcmVz ZXRtdXN0IChtcCk7CiAgICAgICAgICAgbXAtPmJlZ2xpbmUgPSB0cnVlOwogICAgICAgICAgIGJy ZWFrOwogICAgICAgICBjYXNlIEVORExJTkU6CisgICAgICAgICAgbXAgPSBhbGxvY211c3QgKG1w KTsKICAgICAgICAgICByZXNldG11c3QgKG1wKTsKICAgICAgICAgICBtcC0+ZW5kbGluZSA9IHRy dWU7CiAgICAgICAgICAgYnJlYWs7CkBAIC0zODg3LDExICszODk4LDYgQEAgZGZhbXVzdCAoc3Ry dWN0IGRmYSAqZCkKICAgICAgICAgY2FzZSBSUEFSRU46CiAgICAgICAgICAgYXNzZXJ0ICghIm5l aXRoZXIgTFBBUkVOIG5vciBSUEFSRU4gbWF5IGFwcGVhciBoZXJlIik7CiAKLSAgICAgICAgY2Fz ZSBTVEFSOgotICAgICAgICBjYXNlIFFNQVJLOgotICAgICAgICAgIGFzc2VydCAobXVzdHMgPCBt cCk7Ci0gICAgICAgICAgLS1tcDsKLSAgICAgICAgICAvKiBGYWxsIHRocm91Z2guICAqLwogICAg ICAgICBjYXNlIEVNUFRZOgogICAgICAgICBjYXNlIEJFR1dPUkQ6CiAgICAgICAgIGNhc2UgRU5E V09SRDoKQEAgLTM5MDAsMTkgKzM5MDYsMjQgQEAgZGZhbXVzdCAoc3RydWN0IGRmYSAqZCkKICAg ICAgICAgY2FzZSBCQUNLUkVGOgogICAgICAgICBjYXNlIEFOWUNIQVI6CiAgICAgICAgIGNhc2Ug TUJDU0VUOgorICAgICAgICAgIG1wID0gYWxsb2NtdXN0IChtcCk7CisgICAgICAgICAgLyogRmFs bCB0aHJvdWdoLiAgKi8KKyAgICAgICAgY2FzZSBTVEFSOgorICAgICAgICBjYXNlIFFNQVJLOgor ICAgICAgICAgIGFzc2VydCAobXAgIT0gTlVMTCk7CiAgICAgICAgICAgcmVzZXRtdXN0IChtcCk7 CiAgICAgICAgICAgYnJlYWs7CiAKICAgICAgICAgY2FzZSBPUjoKLSAgICAgICAgICBhc3NlcnQg KCZtdXN0c1syXSA8PSBtcCk7CisgICAgICAgICAgYXNzZXJ0IChtcCAmJiBtcC0+cHJldik7CiAg ICAgICAgICAgewogICAgICAgICAgICAgY2hhciAqKm5ldzsKICAgICAgICAgICAgIG11c3QgKmxt cDsKICAgICAgICAgICAgIG11c3QgKnJtcDsKICAgICAgICAgICAgIHNpemVfdCBqLCBsbiwgcm4s IG47CiAKLSAgICAgICAgICAgIHJtcCA9IC0tbXA7Ci0gICAgICAgICAgICBsbXAgPSAtLW1wOwor ICAgICAgICAgICAgcm1wID0gbXA7CisgICAgICAgICAgICBsbXAgPSBtcCA9IG1wLT5wcmV2Owog ICAgICAgICAgICAgLyogR3VhcmFudGVlZCB0byBiZS4gIFVubGlrZWx5LCBidXQgLi4uICAqLwog ICAgICAgICAgICAgaWYgKCFTVFJFUSAobG1wLT5pcywgcm1wLT5pcykpCiAgICAgICAgICAgICAg IGxtcC0+aXNbMF0gPSAnXDAnOwpAQCAtMzkzOSwzNiArMzk1MCwzOSBAQCBkZmFtdXN0IChzdHJ1 Y3QgZGZhICpkKQogICAgICAgICAgICAgZnJlZWxpc3QgKGxtcC0+aW4pOwogICAgICAgICAgICAg ZnJlZSAobG1wLT5pbik7CiAgICAgICAgICAgICBsbXAtPmluID0gbmV3OworICAgICAgICAgICAg ZnJlZW11c3QgKHJtcCk7CiAgICAgICAgICAgfQogICAgICAgICAgIGJyZWFrOwogCiAgICAgICAg IGNhc2UgUExVUzoKLSAgICAgICAgICBhc3NlcnQgKG11c3RzIDwgbXApOwotICAgICAgICAgIC0t bXA7CisgICAgICAgICAgYXNzZXJ0IChtcCAhPSBOVUxMKTsKICAgICAgICAgICBtcC0+aXNbMF0g PSAnXDAnOwogICAgICAgICAgIGJyZWFrOwogCiAgICAgICAgIGNhc2UgRU5EOgotICAgICAgICAg IGFzc2VydCAobXAgPT0gJm11c3RzWzFdKTsKLSAgICAgICAgICBmb3IgKGkgPSAwOyBtdXN0c1sw XS5pbltpXSAhPSBOVUxMOyArK2kpCi0gICAgICAgICAgICBpZiAoc3RybGVuIChtdXN0c1swXS5p bltpXSkgPiBzdHJsZW4gKHJlc3VsdCkpCi0gICAgICAgICAgICAgIHJlc3VsdCA9IG11c3RzWzBd LmluW2ldOwotICAgICAgICAgIGlmIChTVFJFUSAocmVzdWx0LCBtdXN0c1swXS5pcykpCisgICAg ICAgICAgYXNzZXJ0ICghbXAgfHwgIW1wLT5wcmV2KTsKKyAgICAgICAgICBpZiAobXApCiAgICAg ICAgICAgICB7Ci0gICAgICAgICAgICAgIGV4YWN0ID0gdHJ1ZTsKLSAgICAgICAgICAgICAgYmVn bGluZSA9IG11c3RzWzBdLmJlZ2xpbmU7Ci0gICAgICAgICAgICAgIGVuZGxpbmUgPSBtdXN0c1sw XS5lbmRsaW5lOworICAgICAgICAgICAgICBmb3IgKGkgPSAwOyBtcC0+aW5baV0gIT0gTlVMTDsg KytpKQorICAgICAgICAgICAgICAgIGlmIChzdHJsZW4gKG1wLT5pbltpXSkgPiBzdHJsZW4gKHJl c3VsdCkpCisgICAgICAgICAgICAgICAgICByZXN1bHQgPSBtcC0+aW5baV07CisgICAgICAgICAg ICAgIGlmIChTVFJFUSAocmVzdWx0LCBtcC0+aXMpKQorICAgICAgICAgICAgICAgIHsKKyAgICAg ICAgICAgICAgICAgIGV4YWN0ID0gdHJ1ZTsKKyAgICAgICAgICAgICAgICAgIGJlZ2xpbmUgPSBt cC0+YmVnbGluZTsKKyAgICAgICAgICAgICAgICAgIGVuZGxpbmUgPSBtcC0+ZW5kbGluZTsKKyAg ICAgICAgICAgICAgICB9CiAgICAgICAgICAgICB9CiAgICAgICAgICAgZ290byBkb25lOwogCiAg ICAgICAgIGNhc2UgQ0FUOgotICAgICAgICAgIGFzc2VydCAoJm11c3RzWzJdIDw9IG1wKTsKKyAg ICAgICAgICBhc3NlcnQgKG1wICYmIG1wLT5wcmV2KTsKICAgICAgICAgICB7CiAgICAgICAgICAg ICBtdXN0ICpsbXA7CiAgICAgICAgICAgICBtdXN0ICpybXA7CiAKLSAgICAgICAgICAgIHJtcCA9 IC0tbXA7Ci0gICAgICAgICAgICBsbXAgPSAtLW1wOworICAgICAgICAgICAgcm1wID0gbXA7Cisg ICAgICAgICAgICBsbXAgPSBtcCA9IG1wLT5wcmV2OwogICAgICAgICAgICAgLyogSW4uICBFdmVy eXRoaW5nIGluIGxlZnQsIHBsdXMgZXZlcnl0aGluZyBpbgogICAgICAgICAgICAgICAgcmlnaHQs IHBsdXMgY29uY2F0ZW5hdGlvbiBvZgogICAgICAgICAgICAgICAgbGVmdCdzIHJpZ2h0IGFuZCBy aWdodCdzIGxlZnQuICAqLwpAQCAtNDAwMyw2ICs0MDE3LDcgQEAgZGZhbXVzdCAoc3RydWN0IGRm YSAqZCkKICAgICAgICAgICAgICAgICBsbXAtPmJlZ2xpbmUgPSBmYWxzZTsKICAgICAgICAgICAg ICAgICBsbXAtPmVuZGxpbmUgPSBmYWxzZTsKICAgICAgICAgICAgICAgfQorICAgICAgICAgICAg ZnJlZW11c3QgKHJtcCk7CiAgICAgICAgICAgfQogICAgICAgICAgIGJyZWFrOwogCkBAIC00MDEx LDYgKzQwMjYsNyBAQCBkZmFtdXN0IChzdHJ1Y3QgZGZhICpkKQogICAgICAgICAgIGdvdG8gZG9u ZTsKIAogICAgICAgICBkZWZhdWx0OgorICAgICAgICAgIG1wID0gYWxsb2NtdXN0IChtcCk7CiAg ICAgICAgICAgcmVzZXRtdXN0IChtcCk7CiAgICAgICAgICAgaWYgKENTRVQgPD0gdCkKICAgICAg ICAgICAgIHsKQEAgLTQwNDAsMTcgKzQwNTYsNiBAQCBkZmFtdXN0IChzdHJ1Y3QgZGZhICpkKQog ICAgICAgICAgIG1wLT5pbiA9IGVubGlzdCAobXAtPmluLCBtcC0+aXMsIDEpOwogICAgICAgICAg IGJyZWFrOwogICAgICAgICB9Ci0jaWZkZWYgREVCVUcKLSAgICAgIGZwcmludGYgKHN0ZGVyciwg IiBub2RlOiAlemQ6IiwgcmkpOwotICAgICAgcHJ0b2sgKGQtPnRva2Vuc1tyaV0pOwotICAgICAg ZnByaW50ZiAoc3RkZXJyLCAiXG4gIGluOiIpOwotICAgICAgZm9yIChpID0gMDsgbXAtPmluW2ld OyArK2kpCi0gICAgICAgIGZwcmludGYgKHN0ZGVyciwgIiBcIiVzXCIiLCBtcC0+aW5baV0pOwot ICAgICAgZnByaW50ZiAoc3RkZXJyLCAiXG4gIGlzOiBcIiVzXCJcbiIsIG1wLT5pcyk7Ci0gICAg ICBmcHJpbnRmIChzdGRlcnIsICIgIGxlZnQ6IFwiJXNcIlxuIiwgbXAtPmxlZnQpOwotICAgICAg ZnByaW50ZiAoc3RkZXJyLCAiICByaWdodDogXCIlc1wiXG4iLCBtcC0+cmlnaHQpOwotI2VuZGlm Ci0gICAgICArK21wOwogICAgIH0KIGRvbmU6CiAgIGlmICgqcmVzdWx0KQpAQCAtNDA2MywxNiAr NDA2OCw4IEBAIGRvbmU6CiAgICAgICBkbS0+bmV4dCA9IGQtPm11c3RzOwogICAgICAgZC0+bXVz dHMgPSBkbTsKICAgICB9Ci0gIG1wID0gbXVzdHM7Ci0gIGZvciAoaSA9IDA7IGkgPD0gZC0+dGlu ZGV4OyArK2kpCi0gICAgewotICAgICAgZnJlZWxpc3QgKG1wW2ldLmluKTsKLSAgICAgIGZyZWUg KG1wW2ldLmluKTsKLSAgICAgIGZyZWUgKG1wW2ldLmxlZnQpOwotICAgICAgZnJlZSAobXBbaV0u cmlnaHQpOwotICAgICAgZnJlZSAobXBbaV0uaXMpOwotICAgIH0KLSAgZnJlZSAobXApOworICBp ZiAobXApCisgICAgZnJlZW11c3QgKG1wKTsKIH0KIAogc3RydWN0IGRmYSAqCi0tIAoxLjkuMgoK --------_5355A2AA00000000948D_MULTIPART_MIXED_-- From debbugs-submit-bounces@debbugs.gnu.org Thu Apr 24 12:46:59 2014 Received: (at 17248-done) by debbugs.gnu.org; 24 Apr 2014 16:46:59 +0000 Received: from localhost ([127.0.0.1]:57460 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WdMna-0005aT-Ed for submit@debbugs.gnu.org; Thu, 24 Apr 2014 12:46:58 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:50993) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WdMnW-0005aG-Tz for 17248-done@debbugs.gnu.org; Thu, 24 Apr 2014 12:46:56 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id B24BE39E8018; Thu, 24 Apr 2014 09:46:53 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Yz3woifuhYH7; Thu, 24 Apr 2014 09:46:48 -0700 (PDT) Received: from penguin.cs.ucla.edu (Penguin.CS.UCLA.EDU [131.179.64.200]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id E2962A60001; Thu, 24 Apr 2014 09:46:48 -0700 (PDT) Message-ID: <53593FF8.6020904@cs.ucla.edu> Date: Thu, 24 Apr 2014 09:46:48 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0 MIME-Version: 1.0 To: Norihiro Tanaka , 17248-done@debbugs.gnu.org Subject: Re: bug#17248: [PATCH] grep: waste of a lot of memory for a large pattern in dfamust References: <20140412151001.2C0C.27F6AC2D@kcn.ne.jp> <20140419000430.701D.27F6AC2D@kcn.ne.jp> <20140422080839.9492.27F6AC2D@kcn.ne.jp> In-Reply-To: <20140422080839.9492.27F6AC2D@kcn.ne.jp> Content-Type: multipart/mixed; boundary="------------090106030001080000080009" X-Spam-Score: -3.0 (---) X-Debbugs-Envelope-To: 17248-done X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.0 (---) This is a multi-part message in MIME format. --------------090106030001080000080009 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Thanks, I installed that, and followed it up with the attached minor cleanup patch. --------------090106030001080000080009 Content-Type: text/x-patch; name="0001-dfa-minor-tuneup-of-dfamust-memory-savings-patch.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0001-dfa-minor-tuneup-of-dfamust-memory-savings-patch.patch" >From 3e66a99da2d0fc06e28fa90f53d0d52d0d5f69f2 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Thu, 24 Apr 2014 09:40:34 -0700 Subject: [PATCH] dfa: minor tuneup of dfamust memory savings patch * src/dfa.c (allocmust): Use xmalloc, not xzalloc. Initialize the must completely, so that the caller need not invoke resetmust. All callers changed. (dfamust): Omit asserts that aren't needed on typical machines where dereferencing NULL dumps core. Don't leak memory if the pattern contains a NUL byte. --- src/dfa.c | 54 ++++++++++++++++++++++++------------------------------ 1 file changed, 24 insertions(+), 30 deletions(-) diff --git a/src/dfa.c b/src/dfa.c index ee1e8e6..8fc3d6f 100644 --- a/src/dfa.c +++ b/src/dfa.c @@ -3828,11 +3828,13 @@ struct must static must * allocmust (must *mp) { - must *new_mp = xzalloc (sizeof *new_mp); + must *new_mp = xmalloc (sizeof *new_mp); new_mp->in = xzalloc (sizeof *new_mp->in); new_mp->left = xzalloc (2); new_mp->right = xzalloc (2); new_mp->is = xzalloc (2); + new_mp->begline = false; + new_mp->endline = false; new_mp->prev = mp; return new_mp; } @@ -3877,12 +3879,10 @@ dfamust (struct dfa *d) { case BEGLINE: mp = allocmust (mp); - resetmust (mp); mp->begline = true; break; case ENDLINE: mp = allocmust (mp); - resetmust (mp); mp->endline = true; break; case LPAREN: @@ -3898,23 +3898,20 @@ dfamust (struct dfa *d) case ANYCHAR: case MBCSET: mp = allocmust (mp); - /* Fall through. */ + break; + case STAR: case QMARK: - assert (mp != NULL); resetmust (mp); break; case OR: - assert (mp && mp->prev); { char **new; - must *lmp; - must *rmp; + must *rmp = mp; + must *lmp = mp = mp->prev; size_t j, ln, rn, n; - rmp = mp; - lmp = mp = mp->prev; /* Guaranteed to be. Unlikely, but ... */ if (!STREQ (lmp->is, rmp->is)) lmp->is[0] = '\0'; @@ -3946,34 +3943,27 @@ dfamust (struct dfa *d) break; case PLUS: - assert (mp != NULL); mp->is[0] = '\0'; break; case END: - assert (!mp || !mp->prev); - if (mp) + assert (!mp->prev); + for (i = 0; mp->in[i] != NULL; ++i) + if (strlen (mp->in[i]) > strlen (result)) + result = mp->in[i]; + if (STREQ (result, mp->is)) { - for (i = 0; mp->in[i] != NULL; ++i) - if (strlen (mp->in[i]) > strlen (result)) - result = mp->in[i]; - if (STREQ (result, mp->is)) - { - exact = true; - begline = mp->begline; - endline = mp->endline; - } + exact = true; + begline = mp->begline; + endline = mp->endline; } goto done; case CAT: - assert (mp && mp->prev); { - must *lmp; - must *rmp; + must *rmp = mp; + must *lmp = mp = mp->prev; - rmp = mp; - lmp = mp = mp->prev; /* In. Everything in left, plus everything in right, plus concatenation of left's right and right's left. */ @@ -4018,7 +4008,6 @@ dfamust (struct dfa *d) default: mp = allocmust (mp); - resetmust (mp); if (CSET <= t) { /* If T is a singleton, or if case-folding in a unibyte @@ -4059,8 +4048,13 @@ done: dm->next = d->musts; d->musts = dm; } - if (mp) - freemust (mp); + + while (mp) + { + must *prev = mp->prev; + freemust (mp); + mp = prev; + } } struct dfa * -- 1.9.0 --------------090106030001080000080009-- From debbugs-submit-bounces@debbugs.gnu.org Fri May 09 21:05:43 2014 Received: (at 17248-done) by debbugs.gnu.org; 10 May 2014 01:05:43 +0000 Received: from localhost ([127.0.0.1]:57423 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WivjR-0003JY-TJ for submit@debbugs.gnu.org; Fri, 09 May 2014 21:05:42 -0400 Received: from mailgw04.kcn.ne.jp ([61.86.7.211]:40860) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WivjL-0003JH-B1 for 17248-done@debbugs.gnu.org; Fri, 09 May 2014 21:05:36 -0400 Received: from imp01 (mailgw5.kcn.ne.jp [61.86.15.231]) by mailgw04.kcn.ne.jp (Postfix) with ESMTP id 99A606C1390 for <17248-done@debbugs.gnu.org>; Sat, 10 May 2014 10:05:31 +0900 (JST) Received: from mail03.kcn.ne.jp ([61.86.6.182]) by imp01 with bizsmtp id 015X1o00R3veGq50115X5i; Sat, 10 May 2014 10:05:31 +0900 X-OrgRCPT: 17248-done@debbugs.gnu.org Received: from [10.120.1.65] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail03.kcn.ne.jp (Postfix) with ESMTPA id 29819141009A; Sat, 10 May 2014 10:05:31 +0900 (JST) Date: Sat, 10 May 2014 10:05:30 +0900 From: Norihiro Tanaka To: Paul Eggert Subject: Re: bug#17248: [PATCH] grep: waste of a lot of memory for a large pattern in dfamust In-Reply-To: <53593FF8.6020904@cs.ucla.edu> References: <20140422080839.9492.27F6AC2D@kcn.ne.jp> <53593FF8.6020904@cs.ucla.edu> Message-Id: <20140510100518.6A8D.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_536D7A60000000006A84_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 17248-done Cc: 17248-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) --------_536D7A60000000006A84_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit I have added a /* fallthrough */ comment, Jim works so in bug#17350. --------_536D7A60000000006A84_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0001-maint-mark-a-breakless-case-with-fallthrough-comment.patch" Content-Disposition: attachment; filename="0001-maint-mark-a-breakless-case-with-fallthrough-comment.patch" Content-Transfer-Encoding: base64 RnJvbSA4ZGFmYjYwZDdmZGMwYjljZTQ5YTBkZDUxYjA2NDgxMDhlYjM1NzgxIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTYXQsIDEwIE1heSAyMDE0IDA5OjU2OjU3ICswOTAwClN1YmplY3Q6IFtQQVRDSF0gbWFp bnQ6IG1hcmsgYSBicmVha2xlc3MgY2FzZSB3aXRoIC8qIGZhbGx0aHJvdWdoICovIGNvbW1lbnQK Ciogc3JjL2RmYS5jIChkZmFtdXN0KTogQWRkIGNvbW1lbnQgc28gdGhhdCBpdCBpcyBjbGVhciB0 aGF0IHRoZSAiYnJlYWsiCnN0YXRlbWVudCBpcyBkZWxpYmVyYXRlbHkgb21pdHRlZC4KLS0tCiBz cmMvZGZhLmMgfCAzICsrKwogMSBmaWxlIGNoYW5nZWQsIDMgaW5zZXJ0aW9ucygrKQoKZGlmZiAt LWdpdCBhL3NyYy9kZmEuYyBiL3NyYy9kZmEuYwppbmRleCAwYTIyMWY3Li42ODllODA2IDEwMDY0 NAotLS0gYS9zcmMvZGZhLmMKKysrIGIvc3JjL2RmYS5jCkBAIC0zOTI5LDEzICszOTI5LDE2IEBA IGRmYW11c3QgKHN0cnVjdCBkZmEgKmQpCiAgICAgICAgICAgbXAgPSBhbGxvY211c3QgKG1wKTsK ICAgICAgICAgICBtcC0+YmVnbGluZSA9IHRydWU7CiAgICAgICAgICAgYnJlYWs7CisKICAgICAg ICAgY2FzZSBFTkRMSU5FOgogICAgICAgICAgIG1wID0gYWxsb2NtdXN0IChtcCk7CiAgICAgICAg ICAgbXAtPmVuZGxpbmUgPSB0cnVlOwogICAgICAgICAgIGJyZWFrOworCiAgICAgICAgIGNhc2Ug TFBBUkVOOgogICAgICAgICBjYXNlIFJQQVJFTjoKICAgICAgICAgICBhc3NlcnQgKCEibmVpdGhl ciBMUEFSRU4gbm9yIFJQQVJFTiBtYXkgYXBwZWFyIGhlcmUiKTsKKyAgICAgICAgICAvKiBmYWxs dGhyb3VnaCAqLwogCiAgICAgICAgIGNhc2UgRU1QVFk6CiAgICAgICAgIGNhc2UgQkVHV09SRDoK LS0gCjEuOS4yCgo= --------_536D7A60000000006A84_MULTIPART_MIXED_-- From debbugs-submit-bounces@debbugs.gnu.org Fri May 09 21:46:56 2014 Received: (at 17248-done) by debbugs.gnu.org; 10 May 2014 01:46:56 +0000 Received: from localhost ([127.0.0.1]:57433 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WiwNL-0004M0-UP for submit@debbugs.gnu.org; Fri, 09 May 2014 21:46:56 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:58449) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WiwNJ-0004Ll-6p for 17248-done@debbugs.gnu.org; Fri, 09 May 2014 21:46:54 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 26FAE39E8016; Fri, 9 May 2014 18:46:47 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id W3RJq9eX6iXI; Fri, 9 May 2014 18:46:38 -0700 (PDT) Received: from [192.168.1.9] (pool-108-0-233-62.lsanca.fios.verizon.net [108.0.233.62]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 93E2639E8013; Fri, 9 May 2014 18:46:38 -0700 (PDT) Message-ID: <536D84FE.9010505@cs.ucla.edu> Date: Fri, 09 May 2014 18:46:38 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.5.0 MIME-Version: 1.0 To: Norihiro Tanaka Subject: Re: bug#17248: [PATCH] grep: waste of a lot of memory for a large pattern in dfamust References: <20140422080839.9492.27F6AC2D@kcn.ne.jp> <53593FF8.6020904@cs.ucla.edu> <20140510100518.6A8D.27F6AC2D@kcn.ne.jp> In-Reply-To: <20140510100518.6A8D.27F6AC2D@kcn.ne.jp> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -3.0 (---) X-Debbugs-Envelope-To: 17248-done Cc: 17248-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.0 (---) Norihiro Tanaka wrote: > assert (!"neither LPAREN nor RPAREN may appear here"); > + /* fallthrough */ That doesn't fall through, as the 'assert' never returns. From debbugs-submit-bounces@debbugs.gnu.org Fri May 09 23:03:58 2014 Received: (at 17248-done) by debbugs.gnu.org; 10 May 2014 03:03:58 +0000 Received: from localhost ([127.0.0.1]:57448 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WixZu-0006JI-2M for submit@debbugs.gnu.org; Fri, 09 May 2014 23:03:58 -0400 Received: from mailgw06.kcn.ne.jp ([61.86.7.213]:50022) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WixZr-0006J1-AX for 17248-done@debbugs.gnu.org; Fri, 09 May 2014 23:03:56 -0400 Received: from imp01 (mailgw5.kcn.ne.jp [61.86.15.231]) by mailgw06.kcn.ne.jp (Postfix) with ESMTP id 38238D800A for <17248-done@debbugs.gnu.org>; Sat, 10 May 2014 12:03:47 +0900 (JST) Received: from mail03.kcn.ne.jp ([61.86.6.182]) by imp01 with bizsmtp id 033n1o00S3veGq50133nxh; Sat, 10 May 2014 12:03:47 +0900 X-OrgRCPT: 17248-done@debbugs.gnu.org Received: from [10.120.1.65] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail03.kcn.ne.jp (Postfix) with ESMTPA id D3117141009A; Sat, 10 May 2014 12:03:46 +0900 (JST) Date: Sat, 10 May 2014 12:03:46 +0900 From: Norihiro Tanaka To: Paul Eggert Subject: Re: bug#17248: [PATCH] grep: waste of a lot of memory for a large pattern in dfamust In-Reply-To: <536D84FE.9010505@cs.ucla.edu> References: <20140510100518.6A8D.27F6AC2D@kcn.ne.jp> <536D84FE.9010505@cs.ucla.edu> Message-Id: <20140510120345.6A91.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 17248-done Cc: 17248-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) Paul Eggert wrote: > That doesn't fall through, as the 'assert' never returns. Oh! Thanks, I understood it. From unknown Fri Aug 22 01:03:42 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Sat, 07 Jun 2014 11:24:04 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator