cmucl-cvs August 2023

cmucl-cvs@common-lisp.net

1 participants
67 discussions

[Git][cmucl/cmucl][issue-240-add-hashtable-set-exclusive-or] 3 commits: Address #240: Use hashtable for nset-diff, nunion, nintersection
by Raymond Toy (＠rtoy) 25 Aug '23

25 Aug '23

Raymond Toy pushed to branch issue-240-add-hashtable-set-exclusive-or at cmucl / cmucl Commits: 87e54e03 by Raymond Toy at 2023-08-25T14:15:52+00:00 Address #240: Use hashtable for nset-diff, nunion, nintersection - - - - - 4542d55e by Raymond Toy at 2023-08-25T14:16:04+00:00 Merge branch 'issue-240-add-hashtable-for-destructive-set-ops' into 'master' Address #240: Use hashtable for nset-diff, nunion, nintersection See merge request cmucl/cmucl!167 - - - - - d1bf9185 by Raymond Toy at 2023-08-25T08:34:43-07:00 Merge branch 'master' into issue-240-add-hashtable-set-exclusive-or - - - - - 2 changed files: - src/code/list.lisp - tests/sets.lisp Changes: ===================================== src/code/list.lisp ===================================== @@ -749,7 +749,9 @@ (defparameter *min-list-length-for-hashtable* 15) -(declaim (start-block list-to-hashtable union intersection set-difference)) +(declaim (start-block list-to-hashtable + union intersection set-difference + nunion nintersection nset-difference)) ;; Main code to process a set function. INIT-RES initializes the ;; value of RES, which holds the result of the set function. @@ -836,8 +838,6 @@ (process-set nil t)) -(declaim (end-block)) - ;;; Destination and source are setf-able and many-evaluable. Sets the source ;;; to the cdr, and "conses" the 1st elt of source to destination. ;;; @@ -847,19 +847,42 @@ (cdr temp) ,destination ,destination temp))) +;;; Main body for destructive set operations. INIT-RES initializes +;;; the result list. INVERT-P is T if the result of the TEST-FORM +;;; should be inverted. TEST-FORM is the form used for determining +;;; how to update the result. +(defmacro nprocess-set-body (init-res invert-p test-form) + `(let ((res ,init-res) + (list1 list1)) + (do () + ((endp list1)) + (if ,(if invert-p + `(not ,test-form) + test-form) + (steve-splice list1 res) + (setq list1 (cdr list1)))) + res)) + +;; Implementation of the destructive set operations. INIT-RES +;; initializes the value of the result list. INVERT-P indicates +;; whether to invert the test-form used to determine how the result +;; should be updated. +(defmacro nprocess-set (init-res invert-p) + `(let ((hashtable (list-to-hashtable list2 key test test-not))) + (if hashtable + (nprocess-set-body ,init-res ,invert-p + (nth-value 1 (gethash (apply-key key (car list1)) hashtable))) + (nprocess-set-body ,init-res ,invert-p + (with-set-keys (member (apply-key key (car list1)) list2)))))) + + (defun nunion (list1 list2 &key key (test #'eql testp) (test-not nil notp)) "Destructively returns the union list1 and list2." (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((res list2) - (list1 list1)) - (do () - ((endp list1)) - (if (not (with-set-keys (member (apply-key key (car list1)) list2))) - (steve-splice list1 res) - (setf list1 (cdr list1)))) - res)) + + (nprocess-set list2 t)) (defun nintersection (list1 list2 &key key (test #'eql testp) (test-not nil notp)) @@ -867,13 +890,8 @@ (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((res nil) - (list1 list1)) - (do () ((endp list1)) - (if (with-set-keys (member (apply-key key (car list1)) list2)) - (steve-splice list1 res) - (setq list1 (Cdr list1)))) - res)) + + (nprocess-set nil nil)) (defun nset-difference (list1 list2 &key key (test #'eql testp) (test-not nil notp)) @@ -881,14 +899,10 @@ (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((res nil) - (list1 list1)) - (do () ((endp list1)) - (if (not (with-set-keys (member (apply-key key (car list1)) list2))) - (steve-splice list1 res) - (setq list1 (cdr list1)))) - res)) + (nprocess-set nil t)) + +(declaim (end-block)) (defun set-exclusive-or (list1 list2 &key key (test #'eql testp) (test-not nil notp)) ===================================== tests/sets.lisp ===================================== @@ -88,8 +88,37 @@ :test 'eql :test-not 'eql))) - +(define-test nset-diff.1 + (:tag :issues) + ;; From CLHS + (flet + ((test1 (min-length-limit) + (let ((lisp::*min-list-length-for-hashtable* min-length-limit) + (lst1 (list "A" "b" "C" "d")) + (lst2 (list "a" "B" "C" "d"))) + (assert-equal '("b" "A") + (nset-difference lst1 lst2 :test 'equal)) + ;; This isn't specified by the CLHS, but it is what we do. + (assert-equal '("A") lst1)))) + (test1 100) + (test1 1))) + +(define-test nset-diff.key + (:tag :issues) + (flet + ((test (min-length-limit) + ;; From CLHS + (let ((lisp::*min-list-length-for-hashtable* min-length-limit) + (lst1 (list '("a" . "b") '("c" . "d") '("e" . "f"))) + (lst2 (list '("c" . "a") '("e" . "b") '("d" . "a")))) + (assert-equal '(("e" . "f") ("c" . "d")) + (nset-difference lst1 lst2 :test 'equal :key #'cdr)) + ;; This isn't specified by the CLHS, but it is what we do. + (assert-equal '(("a" . "b") ("c" . "d")) lst1)))) + (test 100) + (test 1))) + (define-test union.hash-eql (:tag :issues) ;; For union to use hashtables by making the threshold @@ -173,6 +202,33 @@ :test 'eql :test-not 'eql))) +(define-test nunion.1 + (:tag :issues) + (flet + ((test (min-list-length) + (let ((lisp::*min-list-length-for-hashtable* min-list-length) + (lst1 (list 1 2 '(1 2) "a" "b")) + (lst2 (list 2 3 '(2 3) "B" "C"))) + (assert-equal '("b" "a" (1 2) 1 2 3 (2 3) "B" "C") + (nunion lst1 lst2)) + (assert-equal '(1 2 3 (2 3) "B" "C") + lst1)))) + (test 100) + (test 1))) + +(define-test nintersection.1 + (:tag :issues) + (flet + ((test (min-list-length) + (let ((lisp::*min-list-length-for-hashtable* min-list-length) + (lst1 (list 1 1 2 3 4 'a 'b 'c "A" "B" "C" "d")) + (lst2 (list 1 4 5 'b 'c 'd "a" "B" "c" "D"))) + (assert-equal '(c b 4 1 1) + (nintersection lst1 lst2)) + (assert-equal '(1) lst1)))) + (test 100) + (test 1))) + (define-test subsetp.hash-eq (:tag :issues) View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/fc0d7a8d541e5ccd95a4cc… -- View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/fc0d7a8d541e5ccd95a4cc… You're receiving this email because of your account on gitlab.common-lisp.net.

1 0

[Git][cmucl/cmucl] Pushed new branch issue-240-add-hashtable-set-exclusive-or
by Raymond Toy (＠rtoy) 25 Aug '23

25 Aug '23

Raymond Toy pushed new branch issue-240-add-hashtable-set-exclusive-or at cmucl / cmucl -- View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/tree/issue-240-add-hashtable-s… You're receiving this email because of your account on gitlab.common-lisp.net.

1 0

[Git][cmucl/cmucl][master] 2 commits: Address #240: Use hashtable for nset-diff, nunion, nintersection
by Raymond Toy (＠rtoy) 25 Aug '23

25 Aug '23

Raymond Toy pushed to branch master at cmucl / cmucl Commits: 87e54e03 by Raymond Toy at 2023-08-25T14:15:52+00:00 Address #240: Use hashtable for nset-diff, nunion, nintersection - - - - - 4542d55e by Raymond Toy at 2023-08-25T14:16:04+00:00 Merge branch 'issue-240-add-hashtable-for-destructive-set-ops' into 'master' Address #240: Use hashtable for nset-diff, nunion, nintersection See merge request cmucl/cmucl!167 - - - - - 2 changed files: - src/code/list.lisp - tests/sets.lisp Changes: ===================================== src/code/list.lisp ===================================== @@ -749,7 +749,9 @@ (defparameter *min-list-length-for-hashtable* 15) -(declaim (start-block list-to-hashtable union intersection set-difference)) +(declaim (start-block list-to-hashtable + union intersection set-difference + nunion nintersection nset-difference)) ;; Main code to process a set function. INIT-RES initializes the ;; value of RES, which holds the result of the set function. @@ -836,8 +838,6 @@ (process-set nil t)) -(declaim (end-block)) - ;;; Destination and source are setf-able and many-evaluable. Sets the source ;;; to the cdr, and "conses" the 1st elt of source to destination. ;;; @@ -847,19 +847,42 @@ (cdr temp) ,destination ,destination temp))) +;;; Main body for destructive set operations. INIT-RES initializes +;;; the result list. INVERT-P is T if the result of the TEST-FORM +;;; should be inverted. TEST-FORM is the form used for determining +;;; how to update the result. +(defmacro nprocess-set-body (init-res invert-p test-form) + `(let ((res ,init-res) + (list1 list1)) + (do () + ((endp list1)) + (if ,(if invert-p + `(not ,test-form) + test-form) + (steve-splice list1 res) + (setq list1 (cdr list1)))) + res)) + +;; Implementation of the destructive set operations. INIT-RES +;; initializes the value of the result list. INVERT-P indicates +;; whether to invert the test-form used to determine how the result +;; should be updated. +(defmacro nprocess-set (init-res invert-p) + `(let ((hashtable (list-to-hashtable list2 key test test-not))) + (if hashtable + (nprocess-set-body ,init-res ,invert-p + (nth-value 1 (gethash (apply-key key (car list1)) hashtable))) + (nprocess-set-body ,init-res ,invert-p + (with-set-keys (member (apply-key key (car list1)) list2)))))) + + (defun nunion (list1 list2 &key key (test #'eql testp) (test-not nil notp)) "Destructively returns the union list1 and list2." (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((res list2) - (list1 list1)) - (do () - ((endp list1)) - (if (not (with-set-keys (member (apply-key key (car list1)) list2))) - (steve-splice list1 res) - (setf list1 (cdr list1)))) - res)) + + (nprocess-set list2 t)) (defun nintersection (list1 list2 &key key (test #'eql testp) (test-not nil notp)) @@ -867,13 +890,8 @@ (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((res nil) - (list1 list1)) - (do () ((endp list1)) - (if (with-set-keys (member (apply-key key (car list1)) list2)) - (steve-splice list1 res) - (setq list1 (Cdr list1)))) - res)) + + (nprocess-set nil nil)) (defun nset-difference (list1 list2 &key key (test #'eql testp) (test-not nil notp)) @@ -881,14 +899,10 @@ (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((res nil) - (list1 list1)) - (do () ((endp list1)) - (if (not (with-set-keys (member (apply-key key (car list1)) list2))) - (steve-splice list1 res) - (setq list1 (cdr list1)))) - res)) + (nprocess-set nil t)) + +(declaim (end-block)) (defun set-exclusive-or (list1 list2 &key key (test #'eql testp) (test-not nil notp)) ===================================== tests/sets.lisp ===================================== @@ -88,8 +88,37 @@ :test 'eql :test-not 'eql))) - +(define-test nset-diff.1 + (:tag :issues) + ;; From CLHS + (flet + ((test1 (min-length-limit) + (let ((lisp::*min-list-length-for-hashtable* min-length-limit) + (lst1 (list "A" "b" "C" "d")) + (lst2 (list "a" "B" "C" "d"))) + (assert-equal '("b" "A") + (nset-difference lst1 lst2 :test 'equal)) + ;; This isn't specified by the CLHS, but it is what we do. + (assert-equal '("A") lst1)))) + (test1 100) + (test1 1))) + +(define-test nset-diff.key + (:tag :issues) + (flet + ((test (min-length-limit) + ;; From CLHS + (let ((lisp::*min-list-length-for-hashtable* min-length-limit) + (lst1 (list '("a" . "b") '("c" . "d") '("e" . "f"))) + (lst2 (list '("c" . "a") '("e" . "b") '("d" . "a")))) + (assert-equal '(("e" . "f") ("c" . "d")) + (nset-difference lst1 lst2 :test 'equal :key #'cdr)) + ;; This isn't specified by the CLHS, but it is what we do. + (assert-equal '(("a" . "b") ("c" . "d")) lst1)))) + (test 100) + (test 1))) + (define-test union.hash-eql (:tag :issues) ;; For union to use hashtables by making the threshold @@ -173,6 +202,33 @@ :test 'eql :test-not 'eql))) +(define-test nunion.1 + (:tag :issues) + (flet + ((test (min-list-length) + (let ((lisp::*min-list-length-for-hashtable* min-list-length) + (lst1 (list 1 2 '(1 2) "a" "b")) + (lst2 (list 2 3 '(2 3) "B" "C"))) + (assert-equal '("b" "a" (1 2) 1 2 3 (2 3) "B" "C") + (nunion lst1 lst2)) + (assert-equal '(1 2 3 (2 3) "B" "C") + lst1)))) + (test 100) + (test 1))) + +(define-test nintersection.1 + (:tag :issues) + (flet + ((test (min-list-length) + (let ((lisp::*min-list-length-for-hashtable* min-list-length) + (lst1 (list 1 1 2 3 4 'a 'b 'c "A" "B" "C" "d")) + (lst2 (list 1 4 5 'b 'c 'd "a" "B" "c" "D"))) + (assert-equal '(c b 4 1 1) + (nintersection lst1 lst2)) + (assert-equal '(1) lst1)))) + (test 100) + (test 1))) + (define-test subsetp.hash-eq (:tag :issues) View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/39817da21c213415dd494c… -- View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/39817da21c213415dd494c… You're receiving this email because of your account on gitlab.common-lisp.net.

1 0

[Git][cmucl/cmucl][issue-240-add-hashtable-for-destructive-set-ops] 4 commits: Fix warning that SIGNED-CHAR is also exported from C-CALL
by Raymond Toy (＠rtoy) 25 Aug '23

25 Aug '23

Raymond Toy pushed to branch issue-240-add-hashtable-for-destructive-set-ops at cmucl / cmucl Commits: 427aaa31 by Raymond Toy at 2023-08-22T19:50:31-07:00 Fix warning that SIGNED-CHAR is also exported from C-CALL When we added `c-call:signed-char`, we forgot to also add it to the package exports list for the `c-call` package. Add it to get rid of the compiler warning. - - - - - 9581820a by Raymond Toy at 2023-08-25T13:32:42+00:00 Address #240: Clean up hashtable implementation of set functions - - - - - 39817da2 by Raymond Toy at 2023-08-25T13:32:51+00:00 Merge branch 'issue-240-clean-up-hashtable-impl' into 'master' Address #240: Clean up hashtable implementation of set functions See merge request cmucl/cmucl!168 - - - - - 51df6ed9 by Raymond Toy at 2023-08-25T06:55:36-07:00 Merge branch 'master' into issue-240-add-hashtable-for-destructive-set-ops - - - - - 2 changed files: - src/code/exports.lisp - src/code/list.lisp Changes: ===================================== src/code/exports.lisp ===================================== @@ -169,6 +169,7 @@ (defpackage "C-CALL" (:import-from "COMMON-LISP" "CHAR" "FLOAT") (:export "C-STRING" "CHAR" "DOUBLE" "FLOAT" "INT" "LONG" "SHORT" + "SIGNED-CHAR" "UNSIGNED-CHAR" "UNSIGNED-INT" "UNSIGNED-LONG" "UNSIGNED-SHORT" "LONG-LONG" "UNSIGNED-LONG-LONG" "VOID")) ===================================== src/code/list.lisp ===================================== @@ -752,6 +752,28 @@ (declaim (start-block list-to-hashtable union intersection set-difference nunion nintersection nset-difference)) + +;; Main code to process a set function. INIT-RES initializes the +;; value of RES, which holds the result of the set function. +;; TEST-FORM is a form that tests whether to add the item from LIST1 +;; to RES. +(defmacro process-set-body (init-res invert-p test-form) + `(let ((res ,init-res)) + (dolist (item list1) + (when ,(if invert-p + `(not ,test-form) + test-form) + (push item res))) + res)) + +(defmacro process-set (init-res invert-p) + `(let ((hashtable (list-to-hashtable list2 key test test-not))) + (if hashtable + (process-set-body ,init-res ,invert-p + (nth-value 1 (gethash (apply-key key item) hashtable))) + (process-set-body ,init-res ,invert-p + (with-set-keys (member (apply-key key item) list2)))))) + ;; Convert a list to a hashtable. The hashtable does not handle ;; duplicated values in the list. Returns the hashtable. (defun list-to-hashtable (list key test test-not) @@ -793,17 +815,7 @@ (declare (inline member)) (when (and testp notp) (error (intl:gettext "Test and test-not both supplied."))) - (let ((res list2) - (hashtable (list-to-hashtable list2 key test test-not))) - (cond (hashtable - (dolist (item list1) - (unless (nth-value 1 (gethash (apply-key key item) hashtable)) - (push item res)))) - ((null hashtable) - (dolist (item list1) - (unless (with-set-keys (member (apply-key key item) list2)) - (push item res))))) - res)) + (process-set list2 t)) (defun intersection (list1 list2 &key key @@ -812,20 +824,7 @@ (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((hashtable - (list-to-hashtable list2 key test test-not))) - (cond (hashtable - (let ((res nil)) - (dolist (item list1) - (when (nth-value 1 (gethash (apply-key key item) hashtable)) - (push item res))) - res)) - ((null hashtable) - (let ((res nil)) - (dolist (elt list1) - (if (with-set-keys (member (apply-key key elt) list2)) - (push elt res))) - res))))) + (process-set nil nil)) (defun set-difference (list1 list2 &key key (test #'eql testp) (test-not nil notp)) "Returns the elements of list1 which are not in list2." @@ -836,23 +835,8 @@ (when (null list2) (return-from set-difference list1)) - (let ((hashtable - (list-to-hashtable list2 key test test-not))) - (cond (hashtable - ;; list2 was placed in hash table. - (let ((res nil)) - (dolist (item list1) - (unless (nth-value 1 (gethash (apply-key key item) hashtable)) - (push item res))) - res)) - ((null hashtable) - ;; Default implementation because we didn't create the hash - ;; table. - (let ((res nil)) - (dolist (item list1) - (if (not (with-set-keys (member (apply-key key item) list2))) - (push item res))) - res))))) + (process-set nil t)) + ;;; Destination and source are setf-able and many-evaluable. Sets the source ;;; to the cdr, and "conses" the 1st elt of source to destination. View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/f305c0ee3440ffc83756e5… -- View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/f305c0ee3440ffc83756e5… You're receiving this email because of your account on gitlab.common-lisp.net.

1 0

[Git][cmucl/cmucl][master] 2 commits: Address #240: Clean up hashtable implementation of set functions
by Raymond Toy (＠rtoy) 25 Aug '23

25 Aug '23

Raymond Toy pushed to branch master at cmucl / cmucl Commits: 9581820a by Raymond Toy at 2023-08-25T13:32:42+00:00 Address #240: Clean up hashtable implementation of set functions - - - - - 39817da2 by Raymond Toy at 2023-08-25T13:32:51+00:00 Merge branch 'issue-240-clean-up-hashtable-impl' into 'master' Address #240: Clean up hashtable implementation of set functions See merge request cmucl/cmucl!168 - - - - - 1 changed file: - src/code/list.lisp Changes: ===================================== src/code/list.lisp ===================================== @@ -750,6 +750,28 @@ 15) (declaim (start-block list-to-hashtable union intersection set-difference)) + +;; Main code to process a set function. INIT-RES initializes the +;; value of RES, which holds the result of the set function. +;; TEST-FORM is a form that tests whether to add the item from LIST1 +;; to RES. +(defmacro process-set-body (init-res invert-p test-form) + `(let ((res ,init-res)) + (dolist (item list1) + (when ,(if invert-p + `(not ,test-form) + test-form) + (push item res))) + res)) + +(defmacro process-set (init-res invert-p) + `(let ((hashtable (list-to-hashtable list2 key test test-not))) + (if hashtable + (process-set-body ,init-res ,invert-p + (nth-value 1 (gethash (apply-key key item) hashtable))) + (process-set-body ,init-res ,invert-p + (with-set-keys (member (apply-key key item) list2)))))) + ;; Convert a list to a hashtable. The hashtable does not handle ;; duplicated values in the list. Returns the hashtable. (defun list-to-hashtable (list key test test-not) @@ -791,17 +813,7 @@ (declare (inline member)) (when (and testp notp) (error (intl:gettext "Test and test-not both supplied."))) - (let ((res list2) - (hashtable (list-to-hashtable list2 key test test-not))) - (cond (hashtable - (dolist (item list1) - (unless (nth-value 1 (gethash (apply-key key item) hashtable)) - (push item res)))) - ((null hashtable) - (dolist (item list1) - (unless (with-set-keys (member (apply-key key item) list2)) - (push item res))))) - res)) + (process-set list2 t)) (defun intersection (list1 list2 &key key @@ -810,20 +822,7 @@ (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((hashtable - (list-to-hashtable list2 key test test-not))) - (cond (hashtable - (let ((res nil)) - (dolist (item list1) - (when (nth-value 1 (gethash (apply-key key item) hashtable)) - (push item res))) - res)) - ((null hashtable) - (let ((res nil)) - (dolist (elt list1) - (if (with-set-keys (member (apply-key key elt) list2)) - (push elt res))) - res))))) + (process-set nil nil)) (defun set-difference (list1 list2 &key key (test #'eql testp) (test-not nil notp)) "Returns the elements of list1 which are not in list2." @@ -834,23 +833,8 @@ (when (null list2) (return-from set-difference list1)) - (let ((hashtable - (list-to-hashtable list2 key test test-not))) - (cond (hashtable - ;; list2 was placed in hash table. - (let ((res nil)) - (dolist (item list1) - (unless (nth-value 1 (gethash (apply-key key item) hashtable)) - (push item res))) - res)) - ((null hashtable) - ;; Default implementation because we didn't create the hash - ;; table. - (let ((res nil)) - (dolist (item list1) - (if (not (with-set-keys (member (apply-key key item) list2))) - (push item res))) - res))))) + (process-set nil t)) + (declaim (end-block)) View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/427aaa311105943b771698… -- View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/427aaa311105943b771698… You're receiving this email because of your account on gitlab.common-lisp.net.

1 0

[Git][cmucl/cmucl][master] Fix warning that SIGNED-CHAR is also exported from C-CALL
by Raymond Toy (＠rtoy) 23 Aug '23

23 Aug '23

Raymond Toy pushed to branch master at cmucl / cmucl Commits: 427aaa31 by Raymond Toy at 2023-08-22T19:50:31-07:00 Fix warning that SIGNED-CHAR is also exported from C-CALL When we added `c-call:signed-char`, we forgot to also add it to the package exports list for the `c-call` package. Add it to get rid of the compiler warning. - - - - - 1 changed file: - src/code/exports.lisp Changes: ===================================== src/code/exports.lisp ===================================== @@ -169,6 +169,7 @@ (defpackage "C-CALL" (:import-from "COMMON-LISP" "CHAR" "FLOAT") (:export "C-STRING" "CHAR" "DOUBLE" "FLOAT" "INT" "LONG" "SHORT" + "SIGNED-CHAR" "UNSIGNED-CHAR" "UNSIGNED-INT" "UNSIGNED-LONG" "UNSIGNED-SHORT" "LONG-LONG" "UNSIGNED-LONG-LONG" "VOID")) View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/commit/427aaa311105943b771698b… -- View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/commit/427aaa311105943b771698b… You're receiving this email because of your account on gitlab.common-lisp.net.

1 0

[Git][cmucl/cmucl][issue-240-clean-up-hashtable-impl] 2 commits: Refactor the body of set ops
by Raymond Toy (＠rtoy) 22 Aug '23

22 Aug '23

Raymond Toy pushed to branch issue-240-clean-up-hashtable-impl at cmucl / cmucl Commits: e6f1cc3e by Raymond Toy at 2023-08-22T16:30:18-07:00 Refactor the body of set ops The set functions have basically exactly the same body with the only difference being how the result list is initialized; the test form used to determine how the result list is updated; and whether a hashtable is used or not. Place all of the common stuff in the macro PROCESS-SET and rename the old PROCESS-SET to PROCESS-SET-BODY. - - - - - b4d8cfea by Raymond Toy at 2023-08-22T16:31:34-07:00 Remove commented out code - - - - - 1 changed file: - src/code/list.lisp Changes: ===================================== src/code/list.lisp ===================================== @@ -755,13 +755,23 @@ ;; value of RES, which holds the result of the set function. ;; TEST-FORM is a form that tests whether to add the item from LIST1 ;; to RES. -(defmacro process-set (init-res test-form) +(defmacro process-set-body (init-res invert-p test-form) `(let ((res ,init-res)) (dolist (item list1) - (when ,test-form + (when ,(if invert-p + `(not ,test-form) + test-form) (push item res))) res)) +(defmacro process-set (init-res invert-p) + `(let ((hashtable (list-to-hashtable list2 key test test-not))) + (if hashtable + (process-set-body ,init-res ,invert-p + (nth-value 1 (gethash (apply-key key item) hashtable))) + (process-set-body ,init-res ,invert-p + (with-set-keys (member (apply-key key item) list2)))))) + ;; Convert a list to a hashtable. The hashtable does not handle ;; duplicated values in the list. Returns the hashtable. (defun list-to-hashtable (list key test test-not) @@ -803,10 +813,7 @@ (declare (inline member)) (when (and testp notp) (error (intl:gettext "Test and test-not both supplied."))) - (let ((hashtable (list-to-hashtable list2 key test test-not))) - (if hashtable - (process-set list2 (not (nth-value 1 (gethash (apply-key key item) hashtable)))) - (process-set list2 (not (with-set-keys (member (apply-key key item) list2))))))) + (process-set list2 t)) (defun intersection (list1 list2 &key key @@ -815,11 +822,7 @@ (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((hashtable - (list-to-hashtable list2 key test test-not))) - (if hashtable - (process-set nil (nth-value 1 (gethash (apply-key key item) hashtable))) - (process-set nil (with-set-keys (member (apply-key key item) list2)))))) + (process-set nil nil)) (defun set-difference (list1 list2 &key key (test #'eql testp) (test-not nil notp)) "Returns the elements of list1 which are not in list2." @@ -830,11 +833,7 @@ (when (null list2) (return-from set-difference list1)) - (let ((hashtable - (list-to-hashtable list2 key test test-not))) - (if hashtable - (process-set nil (not (nth-value 1 (gethash (apply-key key item) hashtable)))) - (process-set nil (not (with-set-keys (member (apply-key key item) list2))))))) + (process-set nil t)) (declaim (end-block)) View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/d046100fe1e8dc2aa9e2b5… -- View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/d046100fe1e8dc2aa9e2b5… You're receiving this email because of your account on gitlab.common-lisp.net.

1 0

[Git][cmucl/cmucl][issue-240-add-hashtable-for-destructive-set-ops] Refactor the body of destructive set ops
by Raymond Toy (＠rtoy) 22 Aug '23

22 Aug '23

Raymond Toy pushed to branch issue-240-add-hashtable-for-destructive-set-ops at cmucl / cmucl Commits: f305c0ee by Raymond Toy at 2023-08-22T15:38:51-07:00 Refactor the body of destructive set ops The destructive set functions have basically exactly the same body with the only difference being how the result list is initialized; the test form used to determine how the result list is updated; and whether a hashtable is used or not. Place all of the common stuff in the macro NPROCESS-SET and rename the old NPROCESS-SET to NPROCESS-SET-BODY. - - - - - 1 changed file: - src/code/list.lisp Changes: ===================================== src/code/list.lisp ===================================== @@ -863,47 +863,42 @@ (cdr temp) ,destination ,destination temp))) -;;; Main processing for destructive set operations. Like PROCESS-SET with same args, -;;; but for destructive operations. -(defmacro nprocess-set (init-res test-form) +;;; Main body for destructive set operations. INIT-RES initializes +;;; the result list. INVERT-P is T if the result of the TEST-FORM +;;; should be inverted. TEST-FORM is the form used for determining +;;; how to update the result. +(defmacro nprocess-set-body (init-res invert-p test-form) `(let ((res ,init-res) (list1 list1)) (do () ((endp list1)) - (if ,test-form + (if ,(if invert-p + `(not ,test-form) + test-form) (steve-splice list1 res) (setq list1 (cdr list1)))) res)) +;; Implementation of the destructive set operations. INIT-RES +;; initializes the value of the result list. INVERT-P indicates +;; whether to invert the test-form used to determine how the result +;; should be updated. +(defmacro nprocess-set (init-res invert-p) + `(let ((hashtable (list-to-hashtable list2 key test test-not))) + (if hashtable + (nprocess-set-body ,init-res ,invert-p + (nth-value 1 (gethash (apply-key key (car list1)) hashtable))) + (nprocess-set-body ,init-res ,invert-p + (with-set-keys (member (apply-key key (car list1)) list2)))))) + (defun nunion (list1 list2 &key key (test #'eql testp) (test-not nil notp)) "Destructively returns the union list1 and list2." (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - - (let (#+nil - (res list2) - (hashtable (list-to-hashtable list2 key test test-not)) - #+nil - (list1 list1)) - (if hashtable - (nprocess-set list2 (not (nth-value 1 (gethash (apply-key key (car list1)) hashtable)))) - (nprocess-set list2 (not (with-set-keys (member (apply-key key (car list1)) list2))))) - #+nil - (macrolet - ((process (test-form) - `(do () - ((endp list1)) - (if (not ,test-form) - (steve-splice list1 res) - (setf list1 (cdr list1)))))) - (cond - (hashtable - (process (nth-value 1 (gethash (apply-key key (car list1)) hashtable)))) - (t - (process (with-set-keys (member (apply-key key (car list1)) list2))))) - res))) + + (nprocess-set list2 t)) (defun nintersection (list1 list2 &key key (test #'eql testp) (test-not nil notp)) @@ -911,26 +906,8 @@ (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let (#+nil - (res nil) - (hashtable (list-to-hashtable list2 key test test-not)) - #+nil - (list1 list1)) - (if hashtable - (nprocess-set nil (nth-value 1 (gethash (apply-key key (car list1)) hashtable))) - (nprocess-set nil (with-set-keys (member (apply-key key (car list1)) list2)))) - #+nil - (macrolet - ((process (test-form) - `(do () ((endp list1)) - (if ,test-form - (steve-splice list1 res) - (setq list1 (Cdr list1)))))) - (cond (hashtable - (process (nth-value 1 (gethash (apply-key key (car list1)) hashtable)))) - (t - (process (with-set-keys (member (apply-key key (car list1)) list2))))) - res))) + + (nprocess-set nil nil)) (defun nset-difference (list1 list2 &key key (test #'eql testp) (test-not nil notp)) @@ -938,26 +915,8 @@ (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let (#+nil - (res nil) - (hashtable (list-to-hashtable list2 key test test-not)) - #+nil - (list1 list1)) - (if hashtable - (nprocess-set nil (not (nth-value 1 (gethash (apply-key key (car list1)) hashtable)))) - (nprocess-set nil (not (with-set-keys (member (apply-key key (car list1)) list2))))) - #+nil - (macrolet - ((process (test-form) - `(do () ((endp list1)) - (if (not ,test-form) - (steve-splice list1 res) - (setq list1 (cdr list1)))))) - (cond (hashtable - (process (nth-value 1 (gethash (apply-key key (car list1)) hashtable)))) - (t - (process (with-set-keys (member (apply-key key (car list1)) list2))))) - res))) + + (nprocess-set nil t)) (declaim (end-block)) View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/commit/f305c0ee3440ffc83756e59… -- View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/commit/f305c0ee3440ffc83756e59… You're receiving this email because of your account on gitlab.common-lisp.net.

1 0

[Git][cmucl/cmucl][issue-240-add-hashtable-for-destructive-set-ops] Add macro NPROCESS-SET for destructive set ops
by Raymond Toy (＠rtoy) 22 Aug '23

22 Aug '23

Raymond Toy pushed to branch issue-240-add-hashtable-for-destructive-set-ops at cmucl / cmucl Commits: 6b3621ac by Raymond Toy at 2023-08-22T15:13:03-07:00 Add macro NPROCESS-SET for destructive set ops The destructive set functions all have basically the same body. The only difference is how to initialize the result list and the test function. Capture this similarity in the macro NPROCESS-SET. - - - - - 1 changed file: - src/code/list.lisp Changes: ===================================== src/code/list.lisp ===================================== @@ -863,15 +863,34 @@ (cdr temp) ,destination ,destination temp))) +;;; Main processing for destructive set operations. Like PROCESS-SET with same args, +;;; but for destructive operations. +(defmacro nprocess-set (init-res test-form) + `(let ((res ,init-res) + (list1 list1)) + (do () + ((endp list1)) + (if ,test-form + (steve-splice list1 res) + (setq list1 (cdr list1)))) + res)) + + (defun nunion (list1 list2 &key key (test #'eql testp) (test-not nil notp)) "Destructively returns the union list1 and list2." (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((res list2) + (let (#+nil + (res list2) (hashtable (list-to-hashtable list2 key test test-not)) + #+nil (list1 list1)) + (if hashtable + (nprocess-set list2 (not (nth-value 1 (gethash (apply-key key (car list1)) hashtable)))) + (nprocess-set list2 (not (with-set-keys (member (apply-key key (car list1)) list2))))) + #+nil (macrolet ((process (test-form) `(do () @@ -892,9 +911,15 @@ (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((res nil) + (let (#+nil + (res nil) (hashtable (list-to-hashtable list2 key test test-not)) - (list1 list1)) + #+nil + (list1 list1)) + (if hashtable + (nprocess-set nil (nth-value 1 (gethash (apply-key key (car list1)) hashtable))) + (nprocess-set nil (with-set-keys (member (apply-key key (car list1)) list2)))) + #+nil (macrolet ((process (test-form) `(do () ((endp list1)) @@ -913,9 +938,15 @@ (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) - (let ((res nil) + (let (#+nil + (res nil) (hashtable (list-to-hashtable list2 key test test-not)) - (list1 list1)) + #+nil + (list1 list1)) + (if hashtable + (nprocess-set nil (not (nth-value 1 (gethash (apply-key key (car list1)) hashtable)))) + (nprocess-set nil (not (with-set-keys (member (apply-key key (car list1)) list2))))) + #+nil (macrolet ((process (test-form) `(do () ((endp list1)) View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/commit/6b3621aca7ff60f1e0d7917… -- View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/commit/6b3621aca7ff60f1e0d7917… You're receiving this email because of your account on gitlab.common-lisp.net.

1 0

[Git][cmucl/cmucl][issue-240-clean-up-hashtable-impl] Add macro PROCESS-SET to handle processing of set functions
by Raymond Toy (＠rtoy) 22 Aug '23

22 Aug '23

Raymond Toy pushed to branch issue-240-clean-up-hashtable-impl at cmucl / cmucl Commits: d046100f by Raymond Toy at 2023-08-22T14:39:12-07:00 Add macro PROCESS-SET to handle processing of set functions All of the (non-destructive) set functions have basically the same processing code. The only difference is how to initialize the result and the test used to determine if an item is to be added to the result. We encapsulate this similarity in the macro `PROCESS-SET` and use it in `union`, `intersection`, and `set-difference`. - - - - - 1 changed file: - src/code/list.lisp Changes: ===================================== src/code/list.lisp ===================================== @@ -750,6 +750,18 @@ 15) (declaim (start-block list-to-hashtable union intersection set-difference)) + +;; Main code to process a set function. INIT-RES initializes the +;; value of RES, which holds the result of the set function. +;; TEST-FORM is a form that tests whether to add the item from LIST1 +;; to RES. +(defmacro process-set (init-res test-form) + `(let ((res ,init-res)) + (dolist (item list1) + (when ,test-form + (push item res))) + res)) + ;; Convert a list to a hashtable. The hashtable does not handle ;; duplicated values in the list. Returns the hashtable. (defun list-to-hashtable (list key test test-not) @@ -791,18 +803,10 @@ (declare (inline member)) (when (and testp notp) (error (intl:gettext "Test and test-not both supplied."))) - (let ((res list2) - (hashtable (list-to-hashtable list2 key test test-not))) - (macrolet - ((process (test-form) - `(dolist (item list1) - (unless ,test-form - (push item res))))) - (cond (hashtable - (process (nth-value 1 (gethash (apply-key key item) hashtable)))) - (t - (process (with-set-keys (member (apply-key key item) list2))))) - res))) + (let ((hashtable (list-to-hashtable list2 key test test-not))) + (if hashtable + (process-set list2 (not (nth-value 1 (gethash (apply-key key item) hashtable)))) + (process-set list2 (not (with-set-keys (member (apply-key key item) list2))))))) (defun intersection (list1 list2 &key key @@ -812,18 +816,10 @@ (if (and testp notp) (error "Test and test-not both supplied.")) (let ((hashtable - (list-to-hashtable list2 key test test-not))) - (macrolet - ((process (test-form) - `(let ((res nil)) - (dolist (item list1) - (if ,test-form - (push item res))) - res))) - (cond (hashtable - (process (nth-value 1 (gethash (apply-key key item) hashtable)))) - (t - (process (with-set-keys (member (apply-key key item) list2)))))))) + (list-to-hashtable list2 key test test-not))) + (if hashtable + (process-set nil (nth-value 1 (gethash (apply-key key item) hashtable))) + (process-set nil (with-set-keys (member (apply-key key item) list2)))))) (defun set-difference (list1 list2 &key key (test #'eql testp) (test-not nil notp)) "Returns the elements of list1 which are not in list2." @@ -835,21 +831,10 @@ (return-from set-difference list1)) (let ((hashtable - (list-to-hashtable list2 key test test-not))) - (macrolet - ((process (test-form) - `(let ((res nil)) - (dolist (item list1) - (if (not ,test-form) - (push item res))) - res))) - - (cond (hashtable - (process (nth-value 1 (gethash (apply-key key item) hashtable)))) - (t - ;; Default implementation because we didn't create the hash - ;; table. - (process (with-set-keys (member (apply-key key item) list2)))))))) + (list-to-hashtable list2 key test test-not))) + (if hashtable + (process-set nil (not (nth-value 1 (gethash (apply-key key item) hashtable)))) + (process-set nil (not (with-set-keys (member (apply-key key item) list2))))))) (declaim (end-block)) View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/commit/d046100fe1e8dc2aa9e2b53… -- View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/commit/d046100fe1e8dc2aa9e2b53… You're receiving this email because of your account on gitlab.common-lisp.net.

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

cmucl-cvs August 2023