From owner-svn-src-all@freebsd.org Sat Sep 28 09:22:53 2019 Return-Path: Delivered-To: svn-src-all@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id BE0411214F3; Sat, 28 Sep 2019 09:22:53 +0000 (UTC) (envelope-from trasz@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) server-signature RSA-PSS (4096 bits) client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 46gNVj3X1Qz41D4; Sat, 28 Sep 2019 09:22:53 +0000 (UTC) (envelope-from trasz@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 5C709274C1; Sat, 28 Sep 2019 09:22:53 +0000 (UTC) (envelope-from trasz@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id x8S9MrMw054556; Sat, 28 Sep 2019 09:22:53 GMT (envelope-from trasz@FreeBSD.org) Received: (from trasz@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id x8S9MqlC054553; Sat, 28 Sep 2019 09:22:52 GMT (envelope-from trasz@FreeBSD.org) Message-Id: <201909280922.x8S9MqlC054553@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: trasz set sender to trasz@FreeBSD.org using -f From: Edward Tomasz Napierala Date: Sat, 28 Sep 2019 09:22:52 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r352837 - in head: share/man/man3 sys/sys X-SVN-Group: head X-SVN-Commit-Author: trasz X-SVN-Commit-Paths: in head: share/man/man3 sys/sys X-SVN-Commit-Revision: 352837 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 28 Sep 2019 09:22:53 -0000 Author: trasz Date: Sat Sep 28 09:22:52 2019 New Revision: 352837 URL: https://svnweb.freebsd.org/changeset/base/352837 Log: Add RB_REINSERT(3), a low overhead alternative to removing a node and reinserting it back with an updated key. This is one of dependencies for the upcoming stats(3) code. Reviewed by: cem Obtained from: Netflix MFC after: 2 weeks Sponsored by: Klara Inc, Netflix Differential Revision: https://reviews.freebsd.org/D21786 Modified: head/share/man/man3/Makefile head/share/man/man3/tree.3 head/sys/sys/tree.h Modified: head/share/man/man3/Makefile ============================================================================== --- head/share/man/man3/Makefile Sat Sep 28 09:12:41 2019 (r352836) +++ head/share/man/man3/Makefile Sat Sep 28 09:22:52 2019 (r352837) @@ -324,6 +324,7 @@ MLINKS+= tree.3 RB_EMPTY.3 \ tree.3 RB_PROTOTYPE_REMOVE.3 \ tree.3 RB_PROTOTYPE_REMOVE_COLOR.3 \ tree.3 RB_PROTOTYPE_STATIC.3 \ + tree.3 RB_REINSERT.3 \ tree.3 RB_REMOVE.3 \ tree.3 RB_RIGHT.3 \ tree.3 RB_ROOT.3 \ Modified: head/share/man/man3/tree.3 ============================================================================== --- head/share/man/man3/tree.3 Sat Sep 28 09:12:41 2019 (r352836) +++ head/share/man/man3/tree.3 Sat Sep 28 09:22:52 2019 (r352837) @@ -30,7 +30,7 @@ .\" .\" $FreeBSD$ .\" -.Dd May 8, 2019 +.Dd September 28, 2019 .Dt TREE 3 .Os .Sh NAME @@ -62,6 +62,7 @@ .Nm RB_PROTOTYPE_NEXT , .Nm RB_PROTOTYPE_PREV , .Nm RB_PROTOTYPE_MINMAX , +.Nm RB_PROTOTYPE_REINSERT , .Nm RB_GENERATE , .Nm RB_GENERATE_STATIC , .Nm RB_GENERATE_INSERT , @@ -73,6 +74,7 @@ .Nm RB_GENERATE_NEXT , .Nm RB_GENERATE_PREV , .Nm RB_GENERATE_MINMAX , +.Nm RB_GENERATE_REINSERT , .Nm RB_ENTRY , .Nm RB_HEAD , .Nm RB_INITIALIZER , @@ -95,7 +97,8 @@ .Nm RB_FOREACH_REVERSE_SAFE , .Nm RB_INIT , .Nm RB_INSERT , -.Nm RB_REMOVE +.Nm RB_REMOVE , +.Nm RB_REINSERT .Nd "implementations of splay and red-black trees" .Sh SYNOPSIS .In sys/tree.h @@ -138,6 +141,7 @@ .Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR .Fn RB_PROTOTYPE_PREV NAME TYPE ATTR .Fn RB_PROTOTYPE_MINMAX NAME TYPE ATTR +.Fn RB_PROTOTYPE_REINSERT NAME TYPE ATTR .Fn RB_GENERATE NAME TYPE FIELD CMP .Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP .Fn RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR @@ -149,6 +153,7 @@ .Fn RB_GENERATE_NEXT NAME TYPE FIELD ATTR .Fn RB_GENERATE_PREV NAME TYPE FIELD ATTR .Fn RB_GENERATE_MINMAX NAME TYPE FIELD ATTR +.Fn RB_GENERATE_REINSERT NAME TYPE FIELD CMP ATTR .Fn RB_ENTRY TYPE .Fn RB_HEAD HEADNAME TYPE .Fn RB_INITIALIZER "RB_HEAD *head" @@ -186,6 +191,8 @@ .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm" .Sh DESCRIPTION These macros define data structures for different types of trees: splay trees and red-black trees. @@ -422,8 +429,9 @@ Individual prototypes can be declared with .Fn RB_PROTOTYPE_NFIND , .Fn RB_PROTOTYPE_NEXT , .Fn RB_PROTOTYPE_PREV , +.Fn RB_PROTOTYPE_MINMAX , and -.Fn RB_PROTOTYPE_MINMAX +.Fn RB_PROTOTYPE_REINSERT in case not all functions are required. The individual prototype macros expect .Fa NAME , @@ -456,8 +464,9 @@ As an alternative individual function bodies are gener .Fn RB_GENERATE_NFIND , .Fn RB_GENERATE_NEXT , .Fn RB_GENERATE_PREV , +.Fn RB_GENERATE_MINMAX , and -.Fn RB_GENERATE_MINMAX +.Fn RB_GENERATE_REINSERT macros. .Pp Finally, @@ -559,6 +568,18 @@ and will be overwritten to provide safe traversal. The .Fn RB_EMPTY macro should be used to check whether a red-black tree is empty. +.Pp +The +.Fn RB_REINSERT +macro updates the position of the element +.Fa elm +in the tree. +This must be called if a member of a +.Nm tree +is modified in a way that affects comparison, such as by modifying +a node's key. +This is a lower overhead alternative to removing the element +and reinserting it again. .Sh EXAMPLES The following example demonstrates how to declare a red-black tree holding integers. Modified: head/sys/sys/tree.h ============================================================================== --- head/sys/sys/tree.h Sat Sep 28 09:12:41 2019 (r352836) +++ head/sys/sys/tree.h Sat Sep 28 09:22:52 2019 (r352837) @@ -393,7 +393,8 @@ struct { \ RB_PROTOTYPE_NFIND(name, type, attr); \ RB_PROTOTYPE_NEXT(name, type, attr); \ RB_PROTOTYPE_PREV(name, type, attr); \ - RB_PROTOTYPE_MINMAX(name, type, attr); + RB_PROTOTYPE_MINMAX(name, type, attr); \ + RB_PROTOTYPE_REINSERT(name, type, attr); #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ attr void name##_RB_INSERT_COLOR(struct name *, struct type *) #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ @@ -412,6 +413,8 @@ struct { \ attr struct type *name##_RB_PREV(struct type *) #define RB_PROTOTYPE_MINMAX(name, type, attr) \ attr struct type *name##_RB_MINMAX(struct name *, int) +#define RB_PROTOTYPE_REINSERT(name, type, attr) \ + attr struct type *name##_RB_REINSERT(struct name *, struct type *) /* Main rb operation. * Moves node close to the key of elm to top @@ -429,8 +432,10 @@ struct { \ RB_GENERATE_NFIND(name, type, field, cmp, attr) \ RB_GENERATE_NEXT(name, type, field, attr) \ RB_GENERATE_PREV(name, type, field, attr) \ - RB_GENERATE_MINMAX(name, type, field, attr) + RB_GENERATE_MINMAX(name, type, field, attr) \ + RB_GENERATE_REINSERT(name, type, field, cmp, attr) + #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ attr void \ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ @@ -758,6 +763,22 @@ name##_RB_MINMAX(struct name *head, int val) \ return (parent); \ } +#define RB_GENERATE_REINSERT(name, type, field, cmp, attr) \ +attr struct type * \ +name##_RB_REINSERT(struct name *head, struct type *elm) \ +{ \ + struct type *cmpelm; \ + if (((cmpelm = RB_PREV(name, head, elm)) != NULL && \ + cmp(cmpelm, elm) >= 0) || \ + ((cmpelm = RB_NEXT(name, head, elm)) != NULL && \ + cmp(elm, cmpelm) >= 0)) { \ + /* XXXLAS: Remove/insert is heavy handed. */ \ + RB_REMOVE(name, head, elm); \ + return (RB_INSERT(name, head, elm)); \ + } \ + return (NULL); \ +} \ + #define RB_NEGINF -1 #define RB_INF 1 @@ -769,6 +790,7 @@ name##_RB_MINMAX(struct name *head, int val) \ #define RB_PREV(name, x, y) name##_RB_PREV(y) #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) +#define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y) #define RB_FOREACH(x, name, head) \ for ((x) = RB_MIN(name, head); \