From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 28082 invoked by alias); 18 May 2017 10:14:54 -0000 Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm Precedence: bulk X-No-Archive: yes List-Id: Zsh Workers List List-Post: List-Help: X-Seq: 41124 Received: (qmail 22095 invoked from network); 18 May 2017 10:14:53 -0000 X-Qmail-Scanner-Diagnostics: from aok120.rev.netart.pl by f.primenet.com.au (envelope-from , uid 7791) with qmail-scanner-2.11 (clamdscan: 0.99.2/21882. spamassassin: 3.4.1. Clear:RC:0(85.128.245.120):SA:0(0.0/5.0):. Processed in 3.841354 secs); 18 May 2017 10:14:53 -0000 X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on f.primenet.com.au X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=unavailable autolearn_force=no version=3.4.1 X-Envelope-From: psprint@zdharma.org X-Qmail-Scanner-Mime-Attachments: | X-Qmail-Scanner-Zip-Files: | Received-SPF: none (ns1.primenet.com.au: domain at zdharma.org does not designate permitted sender hosts) X-Virus-Scanned: by amavisd-new using ClamAV (10) Date: Thu, 18 May 2017 12:14:38 +0200 From: Sebastian Gniazdowski To: zsh-workers@zsh.org Message-ID: Subject: A patch with hashtable optimization, which doesn't work X-Mailer: Airmail (231) MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="591d740e_5bd062c2_6b4c" --591d740e_5bd062c2_6b4c Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Hello, it is really simple to keep collision lists sorted. However, I get error = about typeset not being found. Debugged that typeset is inserted into bui= ltintab. I am pretty exhausted, maybe someone will have a revelation on t= his. Debugged that typeset is being searched in: exec.c:729 if ((cn =3D (Cmdnam) cmdnamtab->getnode(cmdnamtab, arg0))) =7B= at final stage, so it apparently misses builtintab search before. Below i= s the main idea, attached is full patch. - =C2=A0 =C2=A0 =C2=A0 if (ht->cmpnodes(hp->nam, hn->nam) =3D=3D 0) =7B + =C2=A0 =C2=A0 =C2=A0 =C2=A0cres =3D ht->cmpnodes(hp->nam, hn->nam); + =C2=A0 =C2=A0 =C2=A0 if ( cres =3D=3D 0 ) =7B =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 hq->next =3D hn; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 goto replacing; - =C2=A0 =C2=A0 =C2=A0 =7D + =C2=A0 =C2=A0 =C2=A0 =7D else if ( cres > 0 ) =7B + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0/* Pointer =60hp=60 is at 'rig= ht' position - it points + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 * to a greater element than =60= hn=60, so we should + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 * insert at one-before, that = is after =60hq=60 */ + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0hq->next =3D hn; + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0hn->next =3D hp; + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (++ht->ct >=3D ht->hsize * = 2 && =21ht->scan) + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0expandhashtable(= ht); + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return NULL; + =C2=A0 =C2=A0 =C2=A0 =C2=A0=7D -- Sebastian Gniazdowski psprint /at/ zdharma.org --591d740e_5bd062c2_6b4c Content-Type: text/plain Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="hashopt.diff.txt" ZGlmZiAtLWdpdCBhL1NyYy9oYXNodGFibGUuYyBiL1NyYy9oYXNodGFibGUuYwppbmRleCBiYTVm YWFkLi5kODIwZWZkIDEwMDY0NAotLS0gYS9TcmMvaGFzaHRhYmxlLmMKKysrIGIvU3JjL2hhc2h0 YWJsZS5jCkBAIC0xNjIsNiArMTYyLDcgQEAgYWRkaGFzaG5vZGUoSGFzaFRhYmxlIGh0LCBjaGFy ICpuYW0sIHZvaWQgKm5vZGVwdHIpCiBIYXNoTm9kZQogYWRkaGFzaG5vZGUyKEhhc2hUYWJsZSBo dCwgY2hhciAqbmFtLCB2b2lkICpub2RlcHRyKQogeworICAgIGludCBjcmVzOwogICAgIHVuc2ln bmVkIGhhc2h2YWw7CiAgICAgSGFzaE5vZGUgaG4sIGhwLCBocTsKIApAQCAtMTgxLDcgKzE4Miw4 IEBAIGFkZGhhc2hub2RlMihIYXNoVGFibGUgaHQsIGNoYXIgKm5hbSwgdm9pZCAqbm9kZXB0cikK ICAgICB9CiAKICAgICAvKiBlbHNlIGNoZWNrIGlmIHRoZSBmaXJzdCBub2RlIGNvbnRhaW5zIHRo ZSBzYW1lIGtleSAqLwotICAgIGlmIChodC0+Y21wbm9kZXMoaHAtPm5hbSwgaG4tPm5hbSkgPT0g MCkgeworICAgIGNyZXMgPSBodC0+Y21wbm9kZXMoaHAtPm5hbSwgaG4tPm5hbSk7CisgICAgaWYg KCBjcmVzID09IDAgKSB7CiAJaHQtPm5vZGVzW2hhc2h2YWxdID0gaG47CiAJcmVwbGFjaW5nOgog CWhuLT5uZXh0ID0gaHAtPm5leHQ7CkBAIC0xOTYsMjEgKzE5OCwzOSBAQCBhZGRoYXNobm9kZTIo SGFzaFRhYmxlIGh0LCBjaGFyICpuYW0sIHZvaWQgKm5vZGVwdHIpCiAJCWh0LT5zY2FuLT51LnUg PSBobjsKIAl9CiAJcmV0dXJuIGhwOworICAgIH0gZWxzZSBpZiAoIGNyZXMgPiAwICkgeworICAg ICAgICAvKiBJbnNlcnQgaW4gZnJvbnQgb2YgdGhlIGxpc3QsIGJlY2F1c2UgZmlyc3QKKyAgICAg ICAgICogZWxlbWVudCwgbm9kZXNbaGFzaHZhbF0sIGlzIGxhcmdlciwgc28gbmV3CisgICAgICAg ICAqIGVsZW1lbnQgaGFzIHRvIGJlIGJlZm9yZSBpdCAqLworICAgICAgICBobi0+bmV4dCA9IGhw OworICAgICAgICBodC0+bm9kZXNbaGFzaHZhbF0gPSBobjsKKwlpZiAoKytodC0+Y3QgPj0gaHQt PmhzaXplICogMiAmJiAhaHQtPnNjYW4pCisJICAgIGV4cGFuZGhhc2h0YWJsZShodCk7CiAgICAg fQogCiAgICAgLyogZWxzZSBydW4gdGhyb3VnaCB0aGUgbGlzdCBhbmQgY2hlY2sgYWxsIHRoZSBr ZXlzICovCiAgICAgaHEgPSBocDsKICAgICBocCA9IGhwLT5uZXh0OwogICAgIGZvciAoOyBocDsg aHEgPSBocCwgaHAgPSBocC0+bmV4dCkgewotCWlmIChodC0+Y21wbm9kZXMoaHAtPm5hbSwgaG4t Pm5hbSkgPT0gMCkgeworICAgICAgICBjcmVzID0gaHQtPmNtcG5vZGVzKGhwLT5uYW0sIGhuLT5u YW0pOworCWlmICggY3JlcyA9PSAwICkgewogCSAgICBocS0+bmV4dCA9IGhuOwogCSAgICBnb3Rv IHJlcGxhY2luZzsKLQl9CisJfSBlbHNlIGlmICggY3JlcyA+IDAgKSB7CisgICAgICAgICAgICAv KiBQb2ludGVyIGBocGAgaXMgYXQgJ3JpZ2h0JyBwb3NpdGlvbiAtIGl0IHBvaW50cworICAgICAg ICAgICAgICogdG8gYSBncmVhdGVyIGVsZW1lbnQgdGhhbiBgaG5gLCBzbyB3ZSBzaG91bGQKKyAg ICAgICAgICAgICAqIGluc2VydCBhdCBvbmUtYmVmb3JlLCB0aGF0IGlzIGFmdGVyIGBocWAgKi8K KyAgICAgICAgICAgIGhxLT5uZXh0ID0gaG47CisgICAgICAgICAgICBobi0+bmV4dCA9IGhwOwor ICAgICAgICAgICAgaWYgKCsraHQtPmN0ID49IGh0LT5oc2l6ZSAqIDIgJiYgIWh0LT5zY2FuKQor ICAgICAgICAgICAgICAgIGV4cGFuZGhhc2h0YWJsZShodCk7CisgICAgICAgICAgICByZXR1cm4g TlVMTDsKKyAgICAgICAgfQogICAgIH0KIAotICAgIC8qIGVsc2UganVzdCBhZGQgaXQgYXQgdGhl IGZyb250IG9mIHRoZSBsaXN0ICovCi0gICAgaG4tPm5leHQgPSBodC0+bm9kZXNbaGFzaHZhbF07 Ci0gICAgaHQtPm5vZGVzW2hhc2h2YWxdID0gaG47CisgICAgLyogZWxzZSBqdXN0IGFkZCBpdCBh dCB0aGUgZW5kIG9mIHRoZSBsaXN0ICovCisgICAgaHEtPm5leHQgPSBobjsKKyAgICBobi0+bmV4 dCA9IE5VTEw7CiAgICAgaWYgKCsraHQtPmN0ID49IGh0LT5oc2l6ZSAqIDIgJiYgIWh0LT5zY2Fu KQogICAgICAgICBleHBhbmRoYXNodGFibGUoaHQpOwogICAgIHJldHVybiBOVUxMOwpAQCAtMjI1 LDE3ICsyNDUsMjAgQEAgYWRkaGFzaG5vZGUyKEhhc2hUYWJsZSBodCwgY2hhciAqbmFtLCB2b2lk ICpub2RlcHRyKQogbW9kX2V4cG9ydCBIYXNoTm9kZQogZ2V0aGFzaG5vZGUoSGFzaFRhYmxlIGh0 LCBjb25zdCBjaGFyICpuYW0pCiB7CisgICAgaW50IGNyZXM7CiAgICAgdW5zaWduZWQgaGFzaHZh bDsKICAgICBIYXNoTm9kZSBocDsKIAogICAgIGhhc2h2YWwgPSBodC0+aGFzaChuYW0pICUgaHQt PmhzaXplOwogICAgIGZvciAoaHAgPSBodC0+bm9kZXNbaGFzaHZhbF07IGhwOyBocCA9IGhwLT5u ZXh0KSB7Ci0JaWYgKGh0LT5jbXBub2RlcyhocC0+bmFtLCBuYW0pID09IDApIHsKKyAgICAgICAg Y3JlcyA9IGh0LT5jbXBub2RlcyhocC0+bmFtLCBuYW0pOworCWlmIChjcmVzID09IDApIHsKIAkg ICAgaWYgKGhwLT5mbGFncyAmIERJU0FCTEVEKQogCQlyZXR1cm4gTlVMTDsKIAkgICAgZWxzZQog CQlyZXR1cm4gaHA7Ci0JfQorCX0gZWxzZSBpZiAoY3JlcyA+IDApCisgICAgICAgICAgICByZXR1 cm4gTlVMTDsKICAgICB9CiAgICAgcmV0dXJuIE5VTEw7CiB9CkBAIC0yNDksMTMgKzI3MiwxNyBA QCBnZXRoYXNobm9kZShIYXNoVGFibGUgaHQsIGNvbnN0IGNoYXIgKm5hbSkKIG1vZF9leHBvcnQg SGFzaE5vZGUKIGdldGhhc2hub2RlMihIYXNoVGFibGUgaHQsIGNvbnN0IGNoYXIgKm5hbSkKIHsK KyAgICBpbnQgY3JlczsKICAgICB1bnNpZ25lZCBoYXNodmFsOwogICAgIEhhc2hOb2RlIGhwOwog CiAgICAgaGFzaHZhbCA9IGh0LT5oYXNoKG5hbSkgJSBodC0+aHNpemU7CiAgICAgZm9yIChocCA9 IGh0LT5ub2Rlc1toYXNodmFsXTsgaHA7IGhwID0gaHAtPm5leHQpIHsKLQlpZiAoaHQtPmNtcG5v ZGVzKGhwLT5uYW0sIG5hbSkgPT0gMCkKKyAgICAgICAgY3JlcyA9IGh0LT5jbXBub2RlcyhocC0+ bmFtLCBuYW0pOworCWlmIChjcmVzID09IDApCiAJICAgIHJldHVybiBocDsKKyAgICAgICAgZWxz ZSBpZiAoY3JlcyA+IDApCisgICAgICAgICAgICByZXR1cm4gTlVMTDsKICAgICB9CiAgICAgcmV0 dXJuIE5VTEw7CiB9Cg== --591d740e_5bd062c2_6b4c--