From nobody Mon Jan 10 19:50:29 2022 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id AC6D01954421; Mon, 10 Jan 2022 19:50:29 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4JXkvT2xrWz3NdY; Mon, 10 Jan 2022 19:50:29 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 376D52F2B; Mon, 10 Jan 2022 19:50:29 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 20AJoTvs005049; Mon, 10 Jan 2022 19:50:29 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 20AJoTEv005048; Mon, 10 Jan 2022 19:50:29 GMT (envelope-from git) Date: Mon, 10 Jan 2022 19:50:29 GMT Message-Id: <202201101950.20AJoTEv005048@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Vladimir Kondratyev Subject: git: dd52763387ab - main - LinuxKPI: Import some linux/rbtree.h functions from OpenBSD List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: wulf X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: dd52763387abd18bb6ac510b1148632a13b945f0 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1641844229; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=h9cclHQin/WJZ3dI8NTBfAKK+yrWJxCqcrIOjweIDio=; b=MWlJcBnMHKliWl5Pn2wIbdsBi/4zIm0D4Nv1PtAl1ZuAInc9AcTMCF7tGRAxstIfrXCClO pVLkQDgQQdVNPvLLUpu+Yidqgj62i7sEtwCTg084pVokQ1K8k8X0AiKT883i9AaAt0/esZ CAhA0GEvTLxDTqA/7YIEm6dgF0HraU7m8nBF/5Dbb6edgS3LdiyqXX4hB3ZK7Ys0x47fdK tFZ7vwYPrMPjooHVQb6coZ/FIDXenZdbSSWYNK9DfFmhmOPufWLk+UzIkO7A9ETEE/aseC 2ZY8IM0ojDwIGTIRa0tLLuwCcXdG3Tb2//AhK94mQAhR9Byuza+A300yX+pQjg== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1641844229; a=rsa-sha256; cv=none; b=B8S7zGchtXPOU9EcZWr6GPqAw2+ShMBDbN1JH6qcHQbc952s7EDE1YxiepSBwuznUTothy 6xLaln/A8XIGXi/fkwZTCJtJLbyAPAKsGQKpQNZIXH0mosSavKDqfYE3L8Xjp2/FKYzmax /iPinJpn3qFvalK4o2IbLDdhmC4eZohpT1xRSs0w8/IWr9WA9kKx1beFKFHWJQ3lshz5aG Pr2EZ6LQGpG10GrAs74o5O0BmfRuL1Rx4dX0a+OqxlkPVeOjVIwFVyCKAKGyh8MAGv/nyx 7k9rcD/XL6VJyapdd+ELdQCghp91A/1idpRIjRsudvcKpgrT5VZmsmkOZl+czQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by wulf: URL: https://cgit.FreeBSD.org/src/commit/?id=dd52763387abd18bb6ac510b1148632a13b945f0 commit dd52763387abd18bb6ac510b1148632a13b945f0 Author: Vladimir Kondratyev AuthorDate: 2021-11-05 11:43:31 +0000 Commit: Vladimir Kondratyev CommitDate: 2022-01-10 19:49:36 +0000 LinuxKPI: Import some linux/rbtree.h functions from OpenBSD Required by drm-kmod Obtained from: OpenBSD MFC after: 1 week --- sys/compat/linuxkpi/common/include/linux/rbtree.h | 40 ++++++++++++++++++++++- 1 file changed, 39 insertions(+), 1 deletion(-) diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h index 78da33ad2658..17d87f73ab75 100644 --- a/sys/compat/linuxkpi/common/include/linux/rbtree.h +++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h @@ -59,9 +59,12 @@ int panic_cmp(struct rb_node *one, struct rb_node *two); RB_HEAD(linux_root, rb_node); RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp); +#define rb_parent(r) RB_PARENT(r, __entry) #define rb_entry(ptr, type, member) container_of(ptr, type, member) +#define rb_entry_safe(ptr, type, member) \ + ((ptr) != NULL ? rb_entry(ptr, type, member) : NULL) -#define RB_EMPTY_ROOT(root) RB_EMPTY((struct linux_root *)root) +#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) #define RB_EMPTY_NODE(node) (RB_PARENT(node, __entry) == node) #define RB_CLEAR_NODE(node) RB_SET_PARENT(node, node, __entry) @@ -74,6 +77,41 @@ RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp); #define rb_first(root) RB_MIN(linux_root, (struct linux_root *)(root)) #define rb_last(root) RB_MAX(linux_root, (struct linux_root *)(root)) +static inline struct rb_node * +__rb_deepest_left(struct rb_node *node) +{ + struct rb_node *parent = NULL; + while (node != NULL) { + parent = node; + if (RB_LEFT(node, __entry)) + node = RB_LEFT(node, __entry); + else + node = RB_RIGHT(node, __entry); + } + return (parent); +} + +static inline struct rb_node * +rb_next_postorder(const struct rb_node *node) +{ + struct rb_node *parent = + RB_PARENT(__DECONST(struct rb_node *, node), __entry); + /* left -> right, right -> root */ + if (parent != NULL && + (node == RB_LEFT(parent, __entry)) && + (RB_RIGHT(parent, __entry))) + return (__rb_deepest_left(RB_RIGHT(parent, __entry))); + else + return (parent); +} + +#define rbtree_postorder_for_each_entry_safe(x, y, head, member) \ + for ((x) = rb_entry_safe(__rb_deepest_left((head)->rb_node), \ + __typeof(*x), member); \ + ((x) != NULL) && ((y) = \ + rb_entry_safe(rb_next_postorder(&x->member), typeof(*x), member), 1); \ + (x) = (y)) + static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link)