FreeBSD source tree http://cgit.freebsd.org/src/atom?h=stable%2F13 2023-08-23T17:43:20Z 2023-08-23T17:43:20Z Warner Losh imp@FreeBSD.org 2023-08-22T01:31:02Z urn:sha1:f8167e0404dab9ffeaca95853dd237ab7c587f82 Remove /^\s*\*\n \*\s+\$FreeBSD\$$\n/ Similar commit in current: (cherry picked from commit 95ee2897e98f) 2022-12-19T22:03:13Z Doug Moore dougm@FreeBSD.org 2022-12-19T22:03:13Z urn:sha1:9d4303dbe2c4a901418657ed09c9f7096756e8b3 Rearranging the left, right, and parent pointers for backward compatibility with stable/13 in d8a88ec381498f5942403088d28ee325b92e9a78 is incomplete because it does not change linux/rbtree.h so that it too knows how rb_left and rb_right are redefined. So complete it. Reported by: jon_xyinn.org, jgibbons@protogate.org Tested by: manu, jon_xyinn.org Differential Revision: https://reviews.freebsd.org/D37743 2022-12-16T09:15:28Z Doug Moore dougm@FreeBSD.org 2022-12-16T09:15:28Z urn:sha1:d8a88ec381498f5942403088d28ee325b92e9a78 A change to RB_COLOR_INSERT, when merged into stable/13, broke binary compatibility. For 13, call the new function RB_DO_COLOR_INSERT, and restore the old function with the original name and parameters. Define RB_COLOR_INSERT in tree.h, and remove changes to the linux rbtree header. Another change altered the order of pointers in the RB_ENTRY struct. For 13, restore the original order. Reported by: manu Reviewed by: hselasky Tested by: manu Differential Revision: https://reviews.freebsd.org/D37716 2022-10-12T02:42:55Z Doug Moore dougm@FreeBSD.org 2022-09-13T06:11:47Z urn:sha1:deeaf9c4d85d937d3c935291e913ae614a28f824 Change RB_COLOR_INSERT to take a parent parameter, to avoid looking up a value already available. Make adjustments to a linux rbtree header, which invokes it. Reviewed by: alc, hselasky Differential Revision: https://reviews.freebsd.org/D36114 (cherry picked from commit 4893472c9a18cd8ce3b68d0c54084ef6f0285d0f) 2022-10-01T17:53:06Z Doug Moore dougm@FreeBSD.org 2022-09-08T04:46:19Z urn:sha1:72c99edafa4998652e1347d9bcf4e0989d775313 Change RB_INSERT_COLOR and RB_REMOVE_COLOR so that the blocks of code that are identical except for left and right being exchanged are made only one block with a variable to indicate left- or right-handedness. Rename RB macros so that those not intended for external use begin with an underscore. Add comments to the balancing code so that another might understand it. Reviewed by: alc, kib MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D36393 (cherry picked from commit d0354fa7b6b1931afe1806bd0bfe3ba83e2aeb00) 2022-09-09T17:11:44Z Doug Moore dougm@FreeBSD.org 2022-08-19T23:11:29Z urn:sha1:412f27c18cdf5f3412e4445849e0b787d5437ece RB_ROTATE_LEFT (and it symmetric twin) modify the rb-tree, adjusting pointers so that what started as a proper tree ends up a proper tree. When two consecutive rotations move the same node up the tree, some of the pointers changed in the first rotation are immediately changed again in the second - namely, the pointer from the rising node to its new parent, and the pointer from that parent back to the rising node. This change removes from RB_ROTATE macros the responsibility for managing those two pointers, and leaves it to the code that calls for rotations to fix up those pointers afterward. That drops a comparison and a pair of assignments from every INSERT_COLOR or REMOVE_COLOR call that ends in a double rotation. A side-effect of this change is that the SWAP_CHILD macro must take as a parameter a pointer to the node that is changing children, where it is now computed from the old child. Since this macro is called in a couple of places besides the RB_ROTATE macros, those calls are also affected. Reviewed by: alc MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D36266 (cherry picked from commit 02d0c43c9e53b3055b17719a184a813032040f79) 2022-01-22T19:34:38Z Vladimir Kondratyev wulf@FreeBSD.org 2021-12-19T10:42:42Z urn:sha1:2d0694b9535060abcf376a7ec407093f0cd6d059 MFC after: 1 week Reviewed by: bz, emaste, hselasky, manu Differential Revision: https://reviews.freebsd.org/D33562 (cherry picked from commit 307f78f3ed90a4145eeb2c8cc79bc95b2666f57a) 2022-01-22T19:34:35Z Vladimir Kondratyev wulf@FreeBSD.org 2021-11-06T10:07:02Z urn:sha1:10cb54117ee26ec57b6ba3b551a2212ffdbb06ac Required by drm-kmod MFC after: 1 week Reviewed by: hselasky, manu Differential Revision: https://reviews.freebsd.org/D32869 (cherry picked from commit dbc920bd9a9b413182a1940155539a3144a405aa) 2022-01-22T19:34:35Z Vladimir Kondratyev wulf@FreeBSD.org 2021-11-05T11:43:31Z urn:sha1:c8ddc214cf76785e99358a92700f68c148d63365 Required by drm-kmod Obtained from: OpenBSD MFC after: 1 week (cherry picked from commit dd52763387abd18bb6ac510b1148632a13b945f0) 2020-12-04T15:50:44Z Hans Petter Selasky hselasky@FreeBSD.org 2020-12-04T15:50:44Z urn:sha1:ff15f3f1330ebc878bc18cc9ecaa41d21c44aff7 MFC after: 1 week Sponsored by: Mellanox Technologies // NVIDIA Networking