From unknown Sun Jun 22 07:49:19 2025 X-Loop: help-debbugs@gnu.org Subject: bug#56199: hash table equality predicate [PATCH] Resent-From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 24 Jun 2022 17:21:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 56199 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: 56199@debbugs.gnu.org X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.165609121116728 (code B ref -1); Fri, 24 Jun 2022 17:21:02 +0000 Received: (at submit) by debbugs.gnu.org; 24 Jun 2022 17:20:11 +0000 Received: from localhost ([127.0.0.1]:43404 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o4myZ-0004Lk-J6 for submit@debbugs.gnu.org; Fri, 24 Jun 2022 13:20:11 -0400 Received: from lists.gnu.org ([209.51.188.17]:57168) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o4myX-0004LY-MI for submit@debbugs.gnu.org; Fri, 24 Jun 2022 13:20:10 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:37712) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o4myT-0000zP-Sx for bug-gnu-emacs@gnu.org; Fri, 24 Jun 2022 13:20:07 -0400 Received: from mail75c50.megamailservers.eu ([91.136.10.85]:37050 helo=mail92c50.megamailservers.eu) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o4myQ-00008w-VP for bug-gnu-emacs@gnu.org; Fri, 24 Jun 2022 13:20:05 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1656091196; bh=GKCVD2srbJvCxWU1mMWODUL9pCTFCqMsl5UwYvSqH90=; h=From:Subject:Date:To:From; b=AkF3HSW1bwu2bxaXgHk+loit5wzg7d3axEv40F+/EYFmqY1Xn2ZEiGKNR0hGPpTz0 E8HrBGsWf2w4CrH8dzRcjvvqWZEizTxpvfrOmlJVhj9qxsKOFgxZlXCA6wZAklNNk+ 6eJVq4syHaoncYvnSY4fb1N1178xOij3RbXd8eC4= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c188-150-171-71.bredband.tele2.se [188.150.171.71]) (authenticated bits=0) by mail92c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 25OHJsHo078813 for ; Fri, 24 Jun 2022 17:19:56 +0000 From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Content-Type: multipart/mixed; boundary="Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D" Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Message-Id: <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> Date: Fri, 24 Jun 2022 19:19:54 +0200 X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A782F26.62B5F23C.002C, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE Received-SPF: softfail client-ip=91.136.10.85; envelope-from=mattiase@acm.org; helo=mail92c50.megamailservers.eu X-Spam_score_int: -11 X-Spam_score: -1.2 X-Spam_bar: - X-Spam_report: (-1.2 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_HELO_NONE=0.001, SPF_SOFTFAIL=0.665, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=no autolearn_force=no X-Spam_action: no action X-Spam-Score: -1.3 (-) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 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: -2.3 (--) --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii Recently[1] a predicate for structural equality was requested that also = recurses through hash tables. It showed that Emacs doesn't even come with a way of comparing hash = tables. Third-party implementations exist but if the code quoted in [2] = is representative, perhaps it would make sense to add a = `hash-table-equal-p` predicate? Even implemented entirely in Lisp it would be an order of magnitude = faster (and actually correct). The attached code is not without flaws but provides a rough starting = point. (This is not meant as a strong argument for or against adding it in the = first place.) --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D Content-Disposition: attachment; filename=hash-table-equal-p.diff Content-Type: application/octet-stream; x-unix-mode=0644; name="hash-table-equal-p.diff" Content-Transfer-Encoding: 7bit diff --git a/lisp/emacs-lisp/subr-x.el b/lisp/emacs-lisp/subr-x.el index 9cd793d05c..17ca80a297 100644 --- a/lisp/emacs-lisp/subr-x.el +++ b/lisp/emacs-lisp/subr-x.el @@ -93,6 +93,28 @@ hash-table-values "Return a list of values in HASH-TABLE." (cl-loop for v being the hash-values of hash-table collect v)) +(defun hash-table-equal-p (h1 h2 &optional value-eq) + "Whether the hash tables H1 and H2 are equal with respect to VALUE-EQ. +Equality means that the tables have the same equality predicate +and the same set of key-value pairs where keys are compared by +that predicate and values by VALUE-EQ, which defaults to `eq'." + (or (eq h1 h2) + (and (= (hash-table-count h1) (hash-table-count h2)) + (eq (hash-table-test h1) (hash-table-test h2)) + (progn + (unless value-eq + (setq value-eq #'eq)) + ;; Loop over the physically smaller table. + (when (> (hash-table-size h1) (hash-table-size h2)) + (cl-rotatef h1 h2)) + (catch 'done + (maphash + (lambda (k v) + (unless (funcall value-eq v (gethash k h2 (not v))) + (throw 'done nil))) + h1) + t))))) + (defsubst string-empty-p (string) "Check whether STRING is empty." (string= string "")) diff --git a/test/lisp/emacs-lisp/subr-x-tests.el b/test/lisp/emacs-lisp/subr-x-tests.el index 7f3916c2c0..923155eedb 100644 --- a/test/lisp/emacs-lisp/subr-x-tests.el +++ b/test/lisp/emacs-lisp/subr-x-tests.el @@ -743,6 +743,55 @@ test-with-buffer-unmodified-if-unchanged (with-current-buffer inner (should-not (buffer-modified-p)))))))) +(ert-deftest subr-x--hash-table-equal-p () + (cl-flet ((hashtab (test &rest elts) + (let ((h (make-hash-table :test test))) + (while elts + (let* ((key (pop elts)) + (val (pop elts))) + (puthash key val h))) + h))) + + (let ((h1 (hashtab #'eq 'a (list 1) 'b (list 2)) + (h2 (hashtab #'eq 'a (list 1) 'b (list 2))))) + (should (hash-table-equal-p h1 h2 #'equal)) + (should (hash-table-equal-p h2 h1 #'equal)) + (should (not (hash-table-equal-p h1 h2 #'eq))) + (should (not (hash-table-equal-p h2 h1 #'eq))) + (should (hash-table-equal-p h1 h1 #'eq))) + + (let ((h1 (hashtab #'eql 1 'a 2 'b) + (h2 (hashtab #'equal 1 'a 2 'b)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql 1 'a 2 'a) + (h2 (hashtab #'eql 1 'a)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql 1 'a 2 'a) + (h2 (hashtab #'eql 1 'a 2 'b)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql 1 'a 2 'a) + (h2 (hashtab #'eql 1 'a 3 'a)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql) + (h2 (hashtab #'eql)))) + (should (hash-table-equal-p h1 h2)) + (should (hash-table-equal-p h2 h1))) + + (let ((h1 (make-hash-table :test #'eql :size 1000 :rehash-size 3.5)) + (h2 (hashtab #'eql 10 'a 20 'b))) + (puthash 10 'a h1) + (puthash 20 'b h1) + (should (hash-table-equal-p h1 h2)) + (should (hash-table-equal-p h2 h1))) + )) (provide 'subr-x-tests) ;;; subr-x-tests.el ends here --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=us-ascii -- [1] https://lists.gnu.org/archive/html/emacs-devel/2022-06/msg00444.html [2] https://lists.gnu.org/archive/html/emacs-devel/2022-06/msg00553.html --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D-- From unknown Sun Jun 22 07:49:19 2025 X-Loop: help-debbugs@gnu.org Subject: bug#56199: hash table equality predicate [PATCH] Resent-From: Lars Ingebrigtsen Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 24 Jun 2022 18:22:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 56199 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Cc: 56199@debbugs.gnu.org Received: via spool by 56199-submit@debbugs.gnu.org id=B56199.165609491723242 (code B ref 56199); Fri, 24 Jun 2022 18:22:01 +0000 Received: (at 56199) by debbugs.gnu.org; 24 Jun 2022 18:21:57 +0000 Received: from localhost ([127.0.0.1]:43496 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o4nwK-00062o-T4 for submit@debbugs.gnu.org; Fri, 24 Jun 2022 14:21:57 -0400 Received: from quimby.gnus.org ([95.216.78.240]:34674) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o4nwI-00062a-SA for 56199@debbugs.gnu.org; Fri, 24 Jun 2022 14:21:55 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnus.org; s=20200322; h=Content-Transfer-Encoding:Content-Type:MIME-Version:Message-ID :In-Reply-To:Date:References:Subject:Cc:To:From:Sender:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=wj3DRxetT95Aksat5P7e1DjsRv4iewS59PBRhB4G59Y=; b=LQx76Qfp0tgIq6kz/QC0M6jUiX Tlov6yjb36ATheozl04gsz8Ys0cOPMKvZx0/HtTh0/fVck9ou74TAac2/ydBM7tRv7Dbp0laXHHke 3lIVquoI7uLr9syq+ZgLVku5N86rD86d6ZkQG0XHBViD7BnxCfsE9aezRfaiv3086sTI=; Received: from [84.212.220.105] (helo=xo) by quimby.gnus.org with esmtpsa (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1o4nw9-0003Us-P4; Fri, 24 Jun 2022 20:21:48 +0200 From: Lars Ingebrigtsen References: <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwBAMAAAClLOS0AAAABGdBTUEAALGPC/xhBQAAACBj SFJNAAB6JgAAgIQAAPoAAACA6AAAdTAAAOpgAAA6mAAAF3CculE8AAAAIVBMVEUxLCgiHRlhXFdD Pjr19PDEwbuGgnumo53W1M6AfHb///9QeSwYAAAAAWJLR0QKaND0VgAAAAd0SU1FB+YGGBIUCsf9 kboAAAGoSURBVDjLjZO9b9swEMVPUlJ5lB0IWkWLjNVNdm1UY6BQpUZ/yBCyuV2ySi0Fc3Qlu1TG Fh3y5zZLhpAskBvvh3ePdw8EeK0xmMuKPDOaULQwAnu5KdemSd9IPWOGYTe0gHFFkAaCnoeW4Jmn gWZUW5UnNeAjcj/pvUgf9dstxBo0AfhNm8pe78OoOo1v8pdnq+CKItHhtWfPlf0I/S676xpdKQDc B2YFxeUuDlXzwzlvT885blQFXMRs02KuAoDM8vv2mmrXcvLH0V25yPU8KFudyvlB29GZgrv7ZUtt w5f6QDK/cCNVkyLM8zRfUnUTHOIhJyzCGwX8PZDzQKpOfH3bT3iYDlxyShNFwUMSiww3WPNAf+JZ N2o+K69ylrKeRlgUvbL4eTt8Sh7Jdq8cyz0ev/iodRtLmbSw7BLX+9UPxdniefgssjJVHADkfpBb MSxPSn/y06/YE85WawUELJ4fWdC4WuRUJAsW7xwti/AWjtNLZkgpQJVtSg/wbh/L0AAkG0R50PvO PR8600e3GWbsNtHBhAVbykyKJw8+mrwhgf+W8z7wD1jTW5FlsOchAAAAJXRFWHRkYXRlOmNyZWF0 ZQAyMDIyLTA2LTI0VDE4OjIwOjA5KzAwOjAwteW2KAAAACV0RVh0ZGF0ZTptb2RpZnkAMjAyMi0w Ni0yNFQxODoyMDowOSswMDowMMS4DpQAAAAASUVORK5CYII= X-Now-Playing: Rocketnumbernine's _Meyouweyou_: "Black And Blue" Date: Fri, 24 Jun 2022 20:21:45 +0200 In-Reply-To: <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> ("Mattias =?UTF-8?Q?Engdeg=C3=A5rd?="'s message of "Fri, 24 Jun 2022 19:19:54 +0200") Message-ID: <87zgi1ncqu.fsf@gnus.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Report: Spam detection software, running on the system "quimby.gnus.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see @@CONTACT_ADDRESS@@ for details. Content preview: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= writes: > Even implemented entirely in Lisp it would be an order of magnitude > faster (and actually correct). > > The attached code is not without flaws but provides a rough starting point. > (This is not me [...] Content analysis details: (-2.9 points, 5.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -1.0 ALL_TRUSTED Passed through trusted hosts only via SMTP -1.9 BAYES_00 BODY: Bayes spam probability is 0 to 1% [score: 0.0000] X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 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.3 (---) Mattias Engdeg=C3=A5rd writes: > Even implemented entirely in Lisp it would be an order of magnitude > faster (and actually correct). > > The attached code is not without flaws but provides a rough starting poin= t. > (This is not meant as a strong argument for or against adding it in > the first place.) I can't ever recall wanting to compare two hash tables for equality (like, that's not what you use a hash table for), but since people have apparently been reimplementing this a lot, then I'm for including it. And the implementation looks nice. --=20 (domestic pets only, the antidote for overdose, milk.) bloggy blog: http://lars.ingebrigtsen.no From unknown Sun Jun 22 07:49:19 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.505 (Entity 5.505) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Subject: bug#56199: closed (Re: bug#56199: hash table equality predicate [PATCH]) Message-ID: References: <2AD517D9-A9BC-44E2-A3DB-51AD84D29540@acm.org> <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> X-Gnu-PR-Message: they-closed 56199 X-Gnu-PR-Package: emacs X-Gnu-PR-Keywords: patch Reply-To: 56199@debbugs.gnu.org Date: Sat, 25 Jun 2022 16:57:02 +0000 Content-Type: multipart/mixed; boundary="----------=_1656176222-23962-1" This is a multi-part message in MIME format... ------------=_1656176222-23962-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #56199: hash table equality predicate [PATCH] which was filed against the emacs package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 56199@debbugs.gnu.org. --=20 56199: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D56199 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1656176222-23962-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 56199-done) by debbugs.gnu.org; 25 Jun 2022 16:56:34 +0000 Received: from localhost ([127.0.0.1]:46147 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o595G-0006Dm-H9 for submit@debbugs.gnu.org; Sat, 25 Jun 2022 12:56:34 -0400 Received: from mail33c50.megamailservers.eu ([91.136.10.43]:52382) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o595D-0006Dd-Cm for 56199-done@debbugs.gnu.org; Sat, 25 Jun 2022 12:56:33 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1656176189; bh=1uIK5JPRSyYV6tVKgOS2P1Yu4lD0S8wXlvzi2ofdTpU=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=Aa2zydgJCfJBNoRMpBmHtxQACzM1sUzXjzIru4eQoT2D71iLlKR4SrjqwMgJWqk5y ZNimein+S2X3e4Ck0cFuZ18e7PcLNDgwb7X3vwZfBDDWL4/eJVE0Qsc/pSEwxKuwEq YfYrZio3DvSVP91KGNjGMMgdNiAXHTKmqRUylZKQ= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c188-150-171-71.bredband.tele2.se [188.150.171.71]) (authenticated bits=0) by mail33c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 25PGuSIC024306; Sat, 25 Jun 2022 16:56:29 +0000 Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: Re: bug#56199: hash table equality predicate [PATCH] From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= In-Reply-To: <87zgi1ncqu.fsf@gnus.org> Date: Sat, 25 Jun 2022 18:56:27 +0200 Content-Transfer-Encoding: quoted-printable Message-Id: <2AD517D9-A9BC-44E2-A3DB-51AD84D29540@acm.org> References: <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> <87zgi1ncqu.fsf@gnus.org> To: Lars Ingebrigtsen X-Mailer: Apple Mail (2.3654.120.0.1.13) X-Origin-Country: SE X-Spam-Score: 1.0 (+) X-Debbugs-Envelope-To: 56199-done Cc: 56199-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 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.0 (/) 24 juni 2022 kl. 20.21 skrev Lars Ingebrigtsen : > I can't ever recall wanting to compare two hash tables for equality > (like, that's not what you use a hash table for) No, you're right -- it's better to wait until there is a concrete need = for it. ------------=_1656176222-23962-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 24 Jun 2022 17:20:11 +0000 Received: from localhost ([127.0.0.1]:43404 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o4myZ-0004Lk-J6 for submit@debbugs.gnu.org; Fri, 24 Jun 2022 13:20:11 -0400 Received: from lists.gnu.org ([209.51.188.17]:57168) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o4myX-0004LY-MI for submit@debbugs.gnu.org; Fri, 24 Jun 2022 13:20:10 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:37712) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o4myT-0000zP-Sx for bug-gnu-emacs@gnu.org; Fri, 24 Jun 2022 13:20:07 -0400 Received: from mail75c50.megamailservers.eu ([91.136.10.85]:37050 helo=mail92c50.megamailservers.eu) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o4myQ-00008w-VP for bug-gnu-emacs@gnu.org; Fri, 24 Jun 2022 13:20:05 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1656091196; bh=GKCVD2srbJvCxWU1mMWODUL9pCTFCqMsl5UwYvSqH90=; h=From:Subject:Date:To:From; b=AkF3HSW1bwu2bxaXgHk+loit5wzg7d3axEv40F+/EYFmqY1Xn2ZEiGKNR0hGPpTz0 E8HrBGsWf2w4CrH8dzRcjvvqWZEizTxpvfrOmlJVhj9qxsKOFgxZlXCA6wZAklNNk+ 6eJVq4syHaoncYvnSY4fb1N1178xOij3RbXd8eC4= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c188-150-171-71.bredband.tele2.se [188.150.171.71]) (authenticated bits=0) by mail92c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 25OHJsHo078813 for ; Fri, 24 Jun 2022 17:19:56 +0000 From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= Content-Type: multipart/mixed; boundary="Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D" Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: hash table equality predicate [PATCH] Message-Id: <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> Date: Fri, 24 Jun 2022 19:19:54 +0200 To: bug-gnu-emacs@gnu.org X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A782F26.62B5F23C.002C, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE Received-SPF: softfail client-ip=91.136.10.85; envelope-from=mattiase@acm.org; helo=mail92c50.megamailservers.eu X-Spam_score_int: -11 X-Spam_score: -1.2 X-Spam_bar: - X-Spam_report: (-1.2 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_HELO_NONE=0.001, SPF_SOFTFAIL=0.665, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=no autolearn_force=no X-Spam_action: no action X-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 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: -2.3 (--) --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii Recently[1] a predicate for structural equality was requested that also = recurses through hash tables. It showed that Emacs doesn't even come with a way of comparing hash = tables. Third-party implementations exist but if the code quoted in [2] = is representative, perhaps it would make sense to add a = `hash-table-equal-p` predicate? Even implemented entirely in Lisp it would be an order of magnitude = faster (and actually correct). The attached code is not without flaws but provides a rough starting = point. (This is not meant as a strong argument for or against adding it in the = first place.) --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D Content-Disposition: attachment; filename=hash-table-equal-p.diff Content-Type: application/octet-stream; x-unix-mode=0644; name="hash-table-equal-p.diff" Content-Transfer-Encoding: 7bit diff --git a/lisp/emacs-lisp/subr-x.el b/lisp/emacs-lisp/subr-x.el index 9cd793d05c..17ca80a297 100644 --- a/lisp/emacs-lisp/subr-x.el +++ b/lisp/emacs-lisp/subr-x.el @@ -93,6 +93,28 @@ hash-table-values "Return a list of values in HASH-TABLE." (cl-loop for v being the hash-values of hash-table collect v)) +(defun hash-table-equal-p (h1 h2 &optional value-eq) + "Whether the hash tables H1 and H2 are equal with respect to VALUE-EQ. +Equality means that the tables have the same equality predicate +and the same set of key-value pairs where keys are compared by +that predicate and values by VALUE-EQ, which defaults to `eq'." + (or (eq h1 h2) + (and (= (hash-table-count h1) (hash-table-count h2)) + (eq (hash-table-test h1) (hash-table-test h2)) + (progn + (unless value-eq + (setq value-eq #'eq)) + ;; Loop over the physically smaller table. + (when (> (hash-table-size h1) (hash-table-size h2)) + (cl-rotatef h1 h2)) + (catch 'done + (maphash + (lambda (k v) + (unless (funcall value-eq v (gethash k h2 (not v))) + (throw 'done nil))) + h1) + t))))) + (defsubst string-empty-p (string) "Check whether STRING is empty." (string= string "")) diff --git a/test/lisp/emacs-lisp/subr-x-tests.el b/test/lisp/emacs-lisp/subr-x-tests.el index 7f3916c2c0..923155eedb 100644 --- a/test/lisp/emacs-lisp/subr-x-tests.el +++ b/test/lisp/emacs-lisp/subr-x-tests.el @@ -743,6 +743,55 @@ test-with-buffer-unmodified-if-unchanged (with-current-buffer inner (should-not (buffer-modified-p)))))))) +(ert-deftest subr-x--hash-table-equal-p () + (cl-flet ((hashtab (test &rest elts) + (let ((h (make-hash-table :test test))) + (while elts + (let* ((key (pop elts)) + (val (pop elts))) + (puthash key val h))) + h))) + + (let ((h1 (hashtab #'eq 'a (list 1) 'b (list 2)) + (h2 (hashtab #'eq 'a (list 1) 'b (list 2))))) + (should (hash-table-equal-p h1 h2 #'equal)) + (should (hash-table-equal-p h2 h1 #'equal)) + (should (not (hash-table-equal-p h1 h2 #'eq))) + (should (not (hash-table-equal-p h2 h1 #'eq))) + (should (hash-table-equal-p h1 h1 #'eq))) + + (let ((h1 (hashtab #'eql 1 'a 2 'b) + (h2 (hashtab #'equal 1 'a 2 'b)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql 1 'a 2 'a) + (h2 (hashtab #'eql 1 'a)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql 1 'a 2 'a) + (h2 (hashtab #'eql 1 'a 2 'b)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql 1 'a 2 'a) + (h2 (hashtab #'eql 1 'a 3 'a)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql) + (h2 (hashtab #'eql)))) + (should (hash-table-equal-p h1 h2)) + (should (hash-table-equal-p h2 h1))) + + (let ((h1 (make-hash-table :test #'eql :size 1000 :rehash-size 3.5)) + (h2 (hashtab #'eql 10 'a 20 'b))) + (puthash 10 'a h1) + (puthash 20 'b h1) + (should (hash-table-equal-p h1 h2)) + (should (hash-table-equal-p h2 h1))) + )) (provide 'subr-x-tests) ;;; subr-x-tests.el ends here --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=us-ascii -- [1] https://lists.gnu.org/archive/html/emacs-devel/2022-06/msg00444.html [2] https://lists.gnu.org/archive/html/emacs-devel/2022-06/msg00553.html --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D-- ------------=_1656176222-23962-1-- From unknown Sun Jun 22 07:49:19 2025 X-Loop: help-debbugs@gnu.org Subject: bug#56199: hash table equality predicate [PATCH] Resent-From: Jean Louis Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 26 Jun 2022 14:33:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 56199 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= , Lars Ingebrigtsen Cc: 56199-done@debbugs.gnu.org Received: via spool by 56199-done@debbugs.gnu.org id=D56199.165625393220982 (code D ref 56199); Sun, 26 Jun 2022 14:33:02 +0000 Received: (at 56199-done) by debbugs.gnu.org; 26 Jun 2022 14:32:12 +0000 Received: from localhost ([127.0.0.1]:48496 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o5TJ6-0005SM-4X for submit@debbugs.gnu.org; Sun, 26 Jun 2022 10:32:12 -0400 Received: from stw1.rcdrun.com ([217.170.207.13]:60557) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o5TJ2-0005SC-EK for 56199-done@debbugs.gnu.org; Sun, 26 Jun 2022 10:32:10 -0400 Received: from [154.227.51.100] ([::ffff:154.227.51.100]) (AUTH: PLAIN admin, TLS: TLS1.2,128bits,ECDHE_RSA_AES_128_GCM_SHA256) by stw1.rcdrun.com with ESMTPSA id 0000000000087C51.0000000062B86DE6.000014EC; Sun, 26 Jun 2022 07:32:05 -0700 Date: Sun, 26 Jun 2022 14:30:13 +0000 In-Reply-To: <2AD517D9-A9BC-44E2-A3DB-51AD84D29540@acm.org> References: <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> <87zgi1ncqu.fsf@gnus.org> <2AD517D9-A9BC-44E2-A3DB-51AD84D29540@acm.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable From: Jean Louis Message-ID: <9709BCF8-4AB9-4CDF-B9BF-890D634424AE@gnu.support> X-Spam-Score: -0.0 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 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: -1.0 (-) I use database stored hashes where new edited and updated one shall be comp= ared to the stored one=2E This will become useful=2E Jean