Ignore:
Timestamp:
Jan 23, 2021, 10:25:24 PM (5 years ago)
Author:
Paul Smedley
Message:

Update rbtree to linux 5.10.10 code

Location:
GPL/branches/uniaud32-next/include/linux
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • GPL/branches/uniaud32-next/include/linux/rbtree.h

    r625 r651  
     1/* SPDX-License-Identifier: GPL-2.0-or-later */
    12/*
    23  Red Black Trees
    34  (C) 1999  Andrea Arcangeli <andrea@suse.de>
    45 
    5   This program is free software; you can redistribute it and/or modify
    6   it under the terms of the GNU General Public License as published by
    7   the Free Software Foundation; either version 2 of the License, or
    8   (at your option) any later version.
    9 
    10   This program is distributed in the hope that it will be useful,
    11   but WITHOUT ANY WARRANTY; without even the implied warranty of
    12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    13   GNU General Public License for more details.
    14 
    15   You should have received a copy of the GNU General Public License
    16   along with this program; if not, write to the Free Software
    17   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    186
    197  linux/include/linux/rbtree.h
    … …  
    2412  performances and genericity...
    2513
    26   See Documentation/rbtree.txt for documentation and samples.
     14  See Documentation/core-api/rbtree.rst for documentation and samples.
    2715*/
    28 /* from 4.19.163 */
     16/* from 5.10.10 */
    2917
    3018#ifndef _LINUX_RBTREE_H
    … …  
    4634};
    4735
    48 /*
    49  * Leftmost-cached rbtrees.
    50  *
    51  * We do not cache the rightmost node based on footprint
    52  * size vs number of potential users that could benefit
    53  * from O(1) rb_last(). Just not worth it, users that want
    54  * this feature can always implement the logic explicitly.
    55  * Furthermore, users that want to cache both pointers may
    56  * find it a bit asymmetric, but that's ok.
    57  */
    58 struct rb_root_cached {
    59         struct rb_root rb_root;
    60         struct rb_node *rb_leftmost;
    61 };
    62 
    6336#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
    6437
    6538#define RB_ROOT (struct rb_root) { NULL, }
    66 #define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
    6739#define rb_entry(ptr, type, member) container_of(ptr, type, member)
    6840
    … …  
    8658extern struct rb_node *rb_last(const struct rb_root *);
    8759
    88 extern void rb_insert_color_cached(struct rb_node *,
    89                                    struct rb_root_cached *, bool);
    90 extern void rb_erase_cached(struct rb_node *node, struct rb_root_cached *);
    91 /* Same as rb_first(), but O(1) */
    92 #define rb_first_cached(root) (root)->rb_leftmost
    93 
    9460/* Postorder iteration - always visit the parent after its children */
    9561extern struct rb_node *rb_first_postorder(const struct rb_root *);
    … …  
    10167extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
    10268                                struct rb_root *root);
    103 extern void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new,
    104                                    struct rb_root_cached *root);
    10569
    10670static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
    … …  
    152116             pos = n)
    153117
     118/*
     119 * Leftmost-cached rbtrees.
     120 *
     121 * We do not cache the rightmost node based on footprint
     122 * size vs number of potential users that could benefit
     123 * from O(1) rb_last(). Just not worth it, users that want
     124 * this feature can always implement the logic explicitly.
     125 * Furthermore, users that want to cache both pointers may
     126 * find it a bit asymmetric, but that's ok.
     127 */
     128struct rb_root_cached {
     129        struct rb_root rb_root;
     130        struct rb_node *rb_leftmost;
     131};
     132
     133#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
     134
     135/* Same as rb_first(), but O(1) */
     136#define rb_first_cached(root) (root)->rb_leftmost
     137
     138static inline void rb_insert_color_cached(struct rb_node *node,
     139                                          struct rb_root_cached *root,
     140                                          bool leftmost)
     141{
     142        if (leftmost)
     143                root->rb_leftmost = node;
     144        rb_insert_color(node, &root->rb_root);
     145}
     146
     147static inline void rb_erase_cached(struct rb_node *node,
     148                                   struct rb_root_cached *root)
     149{
     150        if (root->rb_leftmost == node)
     151                root->rb_leftmost = rb_next(node);
     152        rb_erase(node, &root->rb_root);
     153}
     154
     155static inline void rb_replace_node_cached(struct rb_node *victim,
     156                                          struct rb_node *new,
     157                                          struct rb_root_cached *root)
     158{
     159        if (root->rb_leftmost == victim)
     160                root->rb_leftmost = new;
     161        rb_replace_node(victim, new, &root->rb_root);
     162}
     163
    154164#endif  /* _LINUX_RBTREE_H */

  • GPL/branches/uniaud32-next/include/linux/rbtree_augmented.h

    r625 r651  
     1/* SPDX-License-Identifier: GPL-2.0-or-later */
    12/*
    23  Red Black Trees
    … …  
    56  (C) 2012  Michel Lespinasse <walken@google.com>
    67
    7   This program is free software; you can redistribute it and/or modify
    8   it under the terms of the GNU General Public License as published by
    9   the Free Software Foundation; either version 2 of the License, or
    10   (at your option) any later version.
    11 
    12   This program is distributed in the hope that it will be useful,
    13   but WITHOUT ANY WARRANTY; without even the implied warranty of
    14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    15   GNU General Public License for more details.
    16 
    17   You should have received a copy of the GNU General Public License
    18   along with this program; if not, write to the Free Software
    19   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    208
    219  linux/include/linux/rbtree_augmented.h
    2210*/
    23 /* from 4.19.163 */
     11
     12/* from 5.10.10 */
    2413
    2514#ifndef _LINUX_RBTREE_AUGMENTED_H
    … …  
    3524 * The rest are implementation details you are not expected to depend on.
    3625 *
    37  * See Documentation/rbtree.txt for documentation and samples.
     26 * See Documentation/core-api/rbtree.rst for documentation and samples.
    3827 */
    3928
    … …  
    4433};
    4534
    46 extern void __rb_insert_augmented(struct rb_node *node,
    47                                   struct rb_root *root,
    48                                   bool newleft, struct rb_node **leftmost,
     35extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
    4936        void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
     37
    5038/*
    5139 * Fixup the rbtree and update the augmented information when rebalancing.
    … …  
    5341 * On insertion, the user must update the augmented information on the path
    5442 * leading to the inserted node, then call rb_link_node() as usual and
    55  * rb_augment_inserted() instead of the usual rb_insert_color() call.
    56  * If rb_augment_inserted() rebalances the rbtree, it will callback into
     43 * rb_insert_augmented() instead of the usual rb_insert_color() call.
     44 * If rb_insert_augmented() rebalances the rbtree, it will callback into
    5745 * a user provided function to update the augmented information on the
    5846 * affected subtrees.
    5947 */
    60 /*static inline*/ void
     48static inline void
    6149rb_insert_augmented(struct rb_node *node, struct rb_root *root,
    6250                    const struct rb_augment_callbacks *augment)
    6351{
    64         __rb_insert_augmented(node, root, false, NULL, augment->rotate);
    65 }
    66 
    67 /*static inline*/ void
     52        __rb_insert_augmented(node, root, augment->rotate);
     53}
     54
     55static inline void
    6856rb_insert_augmented_cached(struct rb_node *node,
    6957                           struct rb_root_cached *root, bool newleft,
    7058                           const struct rb_augment_callbacks *augment)
    7159{
    72         __rb_insert_augmented(node, &root->rb_root,
    73                               newleft, &root->rb_leftmost, augment->rotate);
    74 }
    75 
    76 #define RB_DECLARE_CALLBACKS(rb/*static*/, rbname, rbstruct, rbfield,   \
    77                              rbtype, rbaugmented, rbcompute)            \
    78 /*static inline*/ void                                                  \
    79 rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)          \
     60        if (newleft)
     61                root->rb_leftmost = node;
     62        rb_insert_augmented(node, &root->rb_root, augment);
     63}
     64
     65/*
     66 * Template for declaring augmented rbtree callbacks (generic case)
     67 *
     68 * RBSTATIC:    'static' or empty
     69 * RBNAME:      name of the rb_augment_callbacks structure
     70 * RBSTRUCT:    struct type of the tree nodes
     71 * RBFIELD:     name of struct rb_node field within RBSTRUCT
     72 * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
     73 * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
     74 */
     75
     76#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,                          \
     77                             RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE) \
     78static inline void                                                      \
     79RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)          \
    8080{                                                                       \
    8181        while (rb != stop) {                                            \
    82                 rbstruct *node = rb_entry(rb, rbstruct, rbfield);       \
    83                 rbtype augmented = rbcompute(node);                     \
    84                 if (node->rbaugmented == augmented)                     \
     82                RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);       \
     83                if (RBCOMPUTE(node, true))                              \
    8584                        break;                                          \
    86                 node->rbaugmented = augmented;                          \
    87                 rb = rb_parent(&node->rbfield);                         \
     85                rb = rb_parent(&node->RBFIELD);                         \
    8886        }                                                               \
    8987}                                                                       \
    90 /*static inline*/ void                                                  \
    91 rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)         \
     88static inline void                                                      \
     89RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)         \
    9290{                                                                       \
    93         rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);            \
    94         rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);            \
    95         new->rbaugmented = old->rbaugmented;                            \
     91        RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);            \
     92        RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);            \
     93        new->RBAUGMENTED = old->RBAUGMENTED;                            \
    9694}                                                                       \
    97 /*static*/ void                                                         \
    98 rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)       \
     95static void                                                             \
     96RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)       \
    9997{                                                                       \
    100         rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);            \
    101         rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);            \
    102         new->rbaugmented = old->rbaugmented;                            \
    103         old->rbaugmented = rbcompute(old);                              \
     98        RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);            \
     99        RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);            \
     100        new->RBAUGMENTED = old->RBAUGMENTED;                            \
     101        RBCOMPUTE(old, false);                                          \
    104102}                                                                       \
    105 rb/*static*/ const struct rb_augment_callbacks rbname = {                       \
    106         .propagate = rbname ## _propagate,                              \
    107         .copy = rbname ## _copy,                                        \
    108         .rotate = rbname ## _rotate                                     \
     103RBSTATIC const struct rb_augment_callbacks RBNAME = {                   \
     104        .propagate = RBNAME ## _propagate,                              \
     105        .copy = RBNAME ## _copy,                                        \
     106        .rotate = RBNAME ## _rotate                                     \
    109107};
     108
     109/*
     110 * Template for declaring augmented rbtree callbacks,
     111 * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
     112 *
     113 * RBSTATIC:    'static' or empty
     114 * RBNAME:      name of the rb_augment_callbacks structure
     115 * RBSTRUCT:    struct type of the tree nodes
     116 * RBFIELD:     name of struct rb_node field within RBSTRUCT
     117 * RBTYPE:      type of the RBAUGMENTED field
     118 * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
     119 * RBCOMPUTE:   name of function that returns the per-node RBTYPE scalar
     120 */
     121
     122#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,         \
     123                                 RBTYPE, RBAUGMENTED, RBCOMPUTE)              \
     124static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit)          \
     125{                                                                             \
     126        RBSTRUCT *child;                                                      \
     127        RBTYPE max = RBCOMPUTE(node);                                         \
     128        if (node->RBFIELD.rb_left) {                                          \
     129                child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD);   \
     130                if (child->RBAUGMENTED > max)                                 \
     131                        max = child->RBAUGMENTED;                             \
     132        }                                                                     \
     133        if (node->RBFIELD.rb_right) {                                         \
     134                child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD);  \
     135                if (child->RBAUGMENTED > max)                                 \
     136                        max = child->RBAUGMENTED;                             \
     137        }                                                                     \
     138        if (exit && node->RBAUGMENTED == max)                                 \
     139                return true;                                                  \
     140        node->RBAUGMENTED = max;                                              \
     141        return false;                                                         \
     142}                                                                             \
     143RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,                                        \
     144                     RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max)
    110145
    111146
    … …  
    122157#define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
    123158
    124 /*static inline*/ void rb_set_parent(struct rb_node *rb, struct rb_node *p)
     159static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
    125160{
    126161        rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
    127162}
    128163
    129 /*static inline*/ void rb_set_parent_color(struct rb_node *rb,
     164static inline void rb_set_parent_color(struct rb_node *rb,
    130165                                       struct rb_node *p, int color)
    131166{
    … …  
    133168}
    134169
    135 /*static inline*/ void
     170static inline void
    136171__rb_change_child(struct rb_node *old, struct rb_node *new,
    137172                  struct rb_node *parent, struct rb_root *root)
    … …  
    147182
    148183#ifndef TARGET_OS2
    149 /*static inline*/ void
     184static inline void
    150185__rb_change_child_rcu(struct rb_node *old, struct rb_node *new,
    151186                      struct rb_node *parent, struct rb_root *root)
    … …  
    164199        void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
    165200
    166 /*static inline*/ struct rb_node *
     201static inline struct rb_node *
    167202__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
    168                      struct rb_node **leftmost,
    169203                     const struct rb_augment_callbacks *augment)
    170204{
    … …  
    173207        struct rb_node *parent, *rebalance;
    174208        unsigned long pc;
    175 
    176         if (leftmost && node == *leftmost)
    177                 *leftmost = rb_next(node);
    178209
    179210        if (!tmp) {
    … …  
    257288
    258289                if (child2) {
    259                         successor->__rb_parent_color = pc;
    260290                        rb_set_parent_color(child2, parent, RB_BLACK);
    261291                        rebalance = NULL;
    262292                } else {
    263                         unsigned long pc2 = successor->__rb_parent_color;
    264                         successor->__rb_parent_color = pc;
    265                         rebalance = __rb_is_black(pc2) ? parent : NULL;
     293                        rebalance = rb_is_black(successor) ? parent : NULL;
    266294                }
     295                successor->__rb_parent_color = pc;
    267296                tmp = successor;
    268297        }
    … …  
    272301}
    273302
    274 /*static inline*/ void
     303static inline void
    275304rb_erase_augmented(struct rb_node *node, struct rb_root *root,
    276305                   const struct rb_augment_callbacks *augment)
    277306{
    278         struct rb_node *rebalance = __rb_erase_augmented(node, root,
    279                                                          NULL, augment);
     307        struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
    280308        if (rebalance)
    281309                __rb_erase_color(rebalance, root, augment->rotate);
    282310}
    283311
    284 /*static inline*/ void
     312static inline void
    285313rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
    286314                          const struct rb_augment_callbacks *augment)
    287315{
    288         struct rb_node *rebalance = __rb_erase_augmented(node, &root->rb_root,
    289                                                          &root->rb_leftmost,
    290                                                          augment);
    291         if (rebalance)
    292                 __rb_erase_color(rebalance, &root->rb_root, augment->rotate);
     316        if (root->rb_leftmost == node)
     317                root->rb_leftmost = rb_next(node);
     318        rb_erase_augmented(node, &root->rb_root, augment);
    293319}
    294320
Note: See TracChangeset for help on using the changeset viewer.