.. SPDX-License-Identifier: GPL-2.0 .. include:: ../disclaimer-zh_CN.rst :Original: Documentation/core-api/rbtree.rst :翻译: å”艺舟 Tang Yizhou <tangyeechou@gmail.com> ========================= Linuxä¸çš„çº¢é»‘æ ‘ï¼ˆrbtree) ========================= :日期: 2007å¹´1月18æ—¥ :作者: Rob Landley <rob@landley.net> ä½•ä¸ºçº¢é»‘æ ‘ï¼Œå®ƒä»¬æœ‰ä»€ä¹ˆç”¨ï¼Ÿ -------------------------- çº¢é»‘æ ‘æ˜¯ä¸€ç§è‡ªå¹³è¡¡äºŒå‰æœç´¢æ ‘,被用æ¥å˜å‚¨å¯æŽ’åºçš„é”®/值数æ®å¯¹ã€‚è¿™ä¸ŽåŸºæ•°æ ‘ï¼ˆè¢«ç”¨æ¥é«˜æ•ˆ å˜å‚¨ç¨€ç–æ•°ç»„ï¼Œå› æ¤ä½¿ç”¨é•¿æ•´åž‹ä¸‹æ ‡æ¥æ’å…¥/访问/åˆ é™¤ç»“ç‚¹ï¼‰å’Œå“ˆå¸Œè¡¨ï¼ˆæ²¡æœ‰ä¿æŒæŽ’åºå› è€Œæ— æ³• 容易地按åºé历,åŒæ—¶å¿…须调节其大å°å’Œå“ˆå¸Œå‡½æ•°ï¼Œç„¶è€Œçº¢é»‘æ ‘å¯ä»¥ä¼˜é›…地伸缩以便å˜å‚¨ä»»æ„ æ•°é‡çš„键)ä¸åŒã€‚ çº¢é»‘æ ‘å’ŒAVLæ ‘ç±»ä¼¼ï¼Œä½†åœ¨æ’å…¥å’Œåˆ é™¤æ—¶æ供了更快的实时有界的最å情况性能(分别最多两次 旋转和三次旋转,æ¥å¹³è¡¡æ ‘),查询时间轻微å˜æ…¢ï¼ˆä½†æ—¶é—´å¤æ‚度ä»ç„¶æ˜¯O(log n))。 引用Linuxæ¯å‘¨æ–°é—»ï¼ˆLinux Weekly News): å†…æ ¸ä¸æœ‰å¤šå¤„çº¢é»‘æ ‘çš„ä½¿ç”¨æ¡ˆä¾‹ã€‚æœ€åŽæœŸé™è°ƒåº¦å™¨å’Œå®Œå…¨å…¬å¹³æŽ’队(CFQ)I/O调度器利用 çº¢é»‘æ ‘è·Ÿè¸ªè¯·æ±‚ï¼›æ•°æ®åŒ…CD/DVD驱动程åºä¹Ÿæ˜¯å¦‚æ¤ã€‚高精度时钟代ç ä½¿ç”¨ä¸€é¢—çº¢é»‘æ ‘ç»„ç»‡ 未完æˆçš„定时器请求。ext3æ–‡ä»¶ç³»ç»Ÿç”¨çº¢é»‘æ ‘è·Ÿè¸ªç›®å½•é¡¹ã€‚è™šæ‹Ÿå†…å˜åŒºåŸŸï¼ˆVMAs)ã€epoll 文件æ述符ã€å¯†ç å¦å¯†é’¥å’Œåœ¨â€œåˆ†å±‚令牌桶â€è°ƒåº¦å™¨ä¸çš„网络数æ®åŒ…éƒ½ç”±çº¢é»‘æ ‘è·Ÿè¸ªã€‚ 本文档涵盖了对Linuxçº¢é»‘æ ‘å®žçŽ°çš„ä½¿ç”¨æ–¹æ³•ã€‚æ›´å¤šå…³äºŽçº¢é»‘æ ‘çš„æ€§è´¨å’Œå®žçŽ°çš„ä¿¡æ¯ï¼Œå‚è§ï¼š Linuxæ¯å‘¨æ–°é—»å…³äºŽçº¢é»‘æ ‘çš„æ–‡ç« https://lwn.net/Articles/184495/ ç»´åŸºç™¾ç§‘çº¢é»‘æ ‘è¯æ¡ https://en.wikipedia.org/wiki/Red-black_tree çº¢é»‘æ ‘çš„Linux实现 ----------------- Linuxçš„çº¢é»‘æ ‘å®žçŽ°åœ¨æ–‡ä»¶â€œlib/rbtree.câ€ä¸ã€‚è¦ä½¿ç”¨å®ƒï¼Œéœ€è¦â€œ#include <linux/rbtree.h>â€ã€‚ Linuxçš„çº¢é»‘æ ‘å®žçŽ°å¯¹é€Ÿåº¦è¿›è¡Œäº†ä¼˜åŒ–ï¼Œå› æ¤æ¯”ä¼ ç»Ÿçš„å®žçŽ°å°‘ä¸€ä¸ªé—´æŽ¥å±‚ï¼ˆæœ‰æ›´å¥½çš„ç¼“å˜å±€éƒ¨æ€§ï¼‰ã€‚ æ¯ä¸ªrb_node结构体的实例嵌入在它管ç†çš„æ•°æ®ç»“æž„ä¸ï¼Œå› æ¤ä¸éœ€è¦é 指针æ¥åˆ†ç¦»rb_node和它 管ç†çš„æ•°æ®ç»“æž„ã€‚ç”¨æˆ·åº”è¯¥ç¼–å†™ä»–ä»¬è‡ªå·±çš„æ ‘æœç´¢å’Œæ’入函数,æ¥è°ƒç”¨å·²æä¾›çš„çº¢é»‘æ ‘å‡½æ•°ï¼Œ 而ä¸æ˜¯ä½¿ç”¨ä¸€ä¸ªæ¯”è¾ƒå›žè°ƒå‡½æ•°æŒ‡é’ˆã€‚åŠ é”代ç ä¹Ÿç•™ç»™çº¢é»‘æ ‘çš„ç”¨æˆ·ç¼–å†™ã€‚ åˆ›å»ºä¸€é¢—çº¢é»‘æ ‘ -------------- çº¢é»‘æ ‘ä¸çš„æ•°æ®ç»“点是包å«rb_node结构体æˆå‘˜çš„结构体:: struct mytype { struct rb_node node; char *keystring; }; 当处ç†ä¸€ä¸ªæŒ‡å‘内嵌rb_node结构体的指针时,包ä½rb_node的结构体å¯ç”¨æ ‡å‡†çš„container_of() å®è®¿é—®ã€‚æ¤å¤–,个体æˆå‘˜å¯ç›´æŽ¥ç”¨rb_entry(node, type, member)访问。 æ¯é¢—çº¢é»‘æ ‘çš„æ ¹æ˜¯ä¸€ä¸ªrb_rootæ•°æ®ç»“构,它由以下方å¼åˆå§‹åŒ–为空: struct rb_root mytree = RB_ROOT; åœ¨ä¸€é¢—çº¢é»‘æ ‘ä¸æœç´¢å€¼ -------------------- ä¸ºä½ çš„æ ‘å†™ä¸€ä¸ªæœç´¢å‡½æ•°æ˜¯ç›¸å½“简å•çš„ï¼šä»Žæ ‘æ ¹å¼€å§‹ï¼Œæ¯”è¾ƒæ¯ä¸ªå€¼ï¼Œç„¶åŽæ ¹æ®éœ€è¦ç»§ç»å‰å¾€å·¦è¾¹æˆ– å³è¾¹çš„分支。 示例:: struct mytype *my_search(struct rb_root *root, char *string) { struct rb_node *node = root->rb_node; while (node) { struct mytype *data = container_of(node, struct mytype, node); int result; result = strcmp(string, data->keystring); if (result < 0) node = node->rb_left; else if (result > 0) node = node->rb_right; else return data; } return NULL; } åœ¨ä¸€é¢—çº¢é»‘æ ‘ä¸æ’å…¥æ•°æ® ---------------------- åœ¨æ ‘ä¸æ’入数æ®çš„æ¥éª¤åŒ…括:首先æœç´¢æ’入新结点的ä½ç½®ï¼Œç„¶åŽæ’å…¥ç»“ç‚¹å¹¶å¯¹æ ‘å†å¹³è¡¡ ("recoloring")。 æ’入的æœç´¢å’Œä¸Šæ–‡çš„æœç´¢ä¸åŒï¼Œå®ƒè¦æ‰¾åˆ°å«æŽ¥æ–°ç»“点的ä½ç½®ã€‚新结点也需è¦ä¸€ä¸ªæŒ‡å‘它的父节点 的链接,以达到å†å¹³è¡¡çš„目的。 示例:: int my_insert(struct rb_root *root, struct mytype *data) { struct rb_node **new = &(root->rb_node), *parent = NULL; /* Figure out where to put new node */ while (*new) { struct mytype *this = container_of(*new, struct mytype, node); int result = strcmp(data->keystring, this->keystring); parent = *new; if (result < 0) new = &((*new)->rb_left); else if (result > 0) new = &((*new)->rb_right); else return FALSE; } /* Add new node and rebalance tree. */ rb_link_node(&data->node, parent, new); rb_insert_color(&data->node, root); return TRUE; } åœ¨ä¸€é¢—çº¢é»‘æ ‘ä¸åˆ 除或替æ¢å·²ç»å˜åœ¨çš„æ•°æ® -------------------------------------- è‹¥è¦ä»Žæ ‘ä¸åˆ 除一个已ç»å˜åœ¨çš„结点,调用:: void rb_erase(struct rb_node *victim, struct rb_root *tree); 示例:: struct mytype *data = mysearch(&mytree, "walrus"); if (data) { rb_erase(&data->node, &mytree); myfree(data); } è‹¥è¦ç”¨ä¸€ä¸ªæ–°ç»“点替æ¢æ ‘ä¸ä¸€ä¸ªå·²ç»å˜åœ¨çš„键值相åŒçš„结点,调用:: void rb_replace_node(struct rb_node *old, struct rb_node *new, struct rb_root *tree); 通过这ç§æ–¹å¼æ›¿æ¢ç»“点ä¸ä¼šå¯¹æ ‘åšé‡æŽ’åºï¼šå¦‚果新结点的键值和旧结点ä¸åŒï¼Œçº¢é»‘æ ‘å¯èƒ½è¢« ç ´å。 (按排åºçš„顺åºï¼‰é历å˜å‚¨åœ¨çº¢é»‘æ ‘ä¸çš„å…ƒç´ ---------------------------------------- 我们æ供了四个函数,用于以排åºçš„æ–¹å¼éåŽ†ä¸€é¢—çº¢é»‘æ ‘çš„å†…å®¹ã€‚è¿™äº›å‡½æ•°å¯ä»¥åœ¨ä»»æ„çº¢é»‘æ ‘ 上工作,并且ä¸éœ€è¦è¢«ä¿®æ”¹æˆ–包装(除éžåŠ é”的目的):: struct rb_node *rb_first(struct rb_root *tree); struct rb_node *rb_last(struct rb_root *tree); struct rb_node *rb_next(struct rb_node *node); struct rb_node *rb_prev(struct rb_node *node); è¦å¼€å§‹è¿ä»£ï¼Œéœ€è¦ä½¿ç”¨ä¸€ä¸ªæŒ‡å‘æ ‘æ ¹çš„æŒ‡é’ˆè°ƒç”¨rb_first()或rb_last()ï¼Œå®ƒå°†è¿”å›žä¸€ä¸ªæŒ‡å‘ æ ‘ä¸ç¬¬ä¸€ä¸ªæˆ–最åŽä¸€ä¸ªå…ƒç´ 所包å«çš„节点结构的指针。è¦ç»§ç»çš„è¯ï¼Œå¯ä»¥åœ¨å½“å‰ç»“点上调用 rb_next()或rb_prev()æ¥èŽ·å–下一个或上一个结点。当没有剩余的结点时,将返回NULL。 è¿ä»£å™¨å‡½æ•°è¿”回一个指å‘被嵌入的rb_node结构体的指针,由æ¤ï¼ŒåŒ…ä½rb_node的结构体å¯ç”¨ æ ‡å‡†çš„container_of()å®è®¿é—®ã€‚æ¤å¤–,个体æˆå‘˜å¯ç›´æŽ¥ç”¨rb_entry(node, type, member) 访问。 示例:: struct rb_node *node; for (node = rb_first(&mytree); node; node = rb_next(node)) printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring); 带缓å˜çš„çº¢é»‘æ ‘ -------------- 计算最左边(最å°çš„)结点是二å‰æœç´¢æ ‘的一个相当常è§çš„任务,例如用于éåŽ†ï¼Œæˆ–ç”¨æˆ·æ ¹æ® ä»–ä»¬è‡ªå·±çš„é€»è¾‘ä¾èµ–一个特定的顺åºã€‚为æ¤ï¼Œç”¨æˆ·å¯ä»¥ä½¿ç”¨'struct rb_root_cached'æ¥ä¼˜åŒ– 时间å¤æ‚度为O(logN)çš„rb_first()的调用,以简å•åœ°èŽ·å–指针,é¿å…äº†æ½œåœ¨çš„æ˜‚è´µçš„æ ‘è¿ä»£ã€‚ 维护æ“作的é¢å¤–è¿è¡Œæ—¶é—´å¼€é”€å¯å¿½ç•¥ï¼Œä¸è¿‡å†…å˜å 用较大。 å’Œrb_root结构体类似,带缓å˜çš„çº¢é»‘æ ‘ç”±ä»¥ä¸‹æ–¹å¼åˆå§‹åŒ–为空:: struct rb_root_cached mytree = RB_ROOT_CACHED; 带缓å˜çš„çº¢é»‘æ ‘åªæ˜¯ä¸€ä¸ªå¸¸è§„çš„rb_rootï¼ŒåŠ ä¸Šä¸€ä¸ªé¢å¤–的指针æ¥ç¼“å˜æœ€å·¦è¾¹çš„节点。这使得 rb_root_cachedå¯ä»¥å˜åœ¨äºŽrb_rootå˜åœ¨çš„任何地方,并且åªéœ€å¢žåŠ å‡ ä¸ªæŽ¥å£æ¥æ”¯æŒå¸¦ç¼“å˜çš„ æ ‘:: struct rb_node *rb_first_cached(struct rb_root_cached *tree); void rb_insert_color_cached(struct rb_node *, struct rb_root_cached *, bool); void rb_erase_cached(struct rb_node *node, struct rb_root_cached *); æ“ä½œå’Œåˆ é™¤ä¹Ÿæœ‰å¯¹åº”çš„å¸¦ç¼“å˜çš„æ ‘çš„è°ƒç”¨:: void rb_insert_augmented_cached(struct rb_node *node, struct rb_root_cached *, bool, struct rb_augment_callbacks *); void rb_erase_augmented_cached(struct rb_node *, struct rb_root_cached *, struct rb_augment_callbacks *); å¯¹å¢žå¼ºåž‹çº¢é»‘æ ‘çš„æ”¯æŒ -------------------- å¢žå¼ºåž‹çº¢é»‘æ ‘æ˜¯ä¸€ç§åœ¨æ¯ä¸ªç»“点里å˜å‚¨äº†â€œä¸€äº›â€é™„åŠ æ•°æ®çš„çº¢é»‘æ ‘ï¼Œå…¶ä¸ç»“点Nçš„é™„åŠ æ•°æ® å¿…é¡»æ˜¯ä»¥Nä¸ºæ ¹çš„åæ ‘ä¸æ‰€æœ‰ç»“ç‚¹çš„å†…å®¹çš„å‡½æ•°ã€‚å®ƒæ˜¯å»ºç«‹åœ¨çº¢é»‘æ ‘åŸºç¡€è®¾æ–½ä¹‹ä¸Šçš„å¯é€‰ç‰¹æ€§ã€‚ 想è¦ä½¿ç”¨è¿™ä¸ªç‰¹æ€§çš„çº¢é»‘æ ‘ç”¨æˆ·ï¼Œæ’å…¥å’Œåˆ é™¤ç»“ç‚¹æ—¶å¿…é¡»è°ƒç”¨å¢žå¼ºåž‹æŽ¥å£å¹¶æ供增强型回调函数。 å®žçŽ°å¢žå¼ºåž‹çº¢é»‘æ ‘æ“作的C文件必须包å«<linux/rbtree_augmented.h>而ä¸æ˜¯<linux/rbtree.h>。 注æ„,linux/rbtree_augmented.hæš´éœ²äº†ä¸€äº›çº¢é»‘æ ‘å®žçŽ°çš„ç»†èŠ‚è€Œä½ ä¸åº”ä¾èµ–它们,请åšæŒ 使用文档记录的API,并且ä¸è¦åœ¨å¤´æ–‡ä»¶ä¸åŒ…å«<linux/rbtree_augmented.h>,以最å°åŒ–ä½ çš„ 用户æ„外地ä¾èµ–这些实现细节的å¯èƒ½ã€‚ æ’入时,用户必须更新通往被æ’入节点的路径上的增强信æ¯ï¼Œç„¶åŽåƒå¾€å¸¸ä¸€æ ·è°ƒç”¨rb_link_node(), 然åŽæ˜¯rb_augment_inserted()而ä¸æ˜¯å¹³æ—¶çš„rb_insert_color()调用。如果 rb_augment_inserted()å†å¹³è¡¡äº†çº¢é»‘æ ‘ï¼Œå®ƒå°†å›žè°ƒè‡³ä¸€ä¸ªç”¨æˆ·æ供的函数æ¥æ›´æ–°å—å½±å“çš„ åæ ‘ä¸Šçš„å¢žå¼ºä¿¡æ¯ã€‚ åˆ é™¤ä¸€ä¸ªç»“ç‚¹æ—¶ï¼Œç”¨æˆ·å¿…é¡»è°ƒç”¨rb_erase_augmented()而ä¸æ˜¯rb_erase()。 rb_erase_augmented()回调至一个用户æ供的函数æ¥æ›´æ–°å—å½±å“çš„åæ ‘ä¸Šçš„å¢žå¼ºä¿¡æ¯ã€‚ 在两ç§æƒ…况下,回调都是通过rb_augment_callbacks结构体æ供的。必须定义3个回调: - ä¸€ä¸ªä¼ æ’回调,它更新一个给定结点和它的祖先们的增强数æ®ï¼Œç›´åˆ°ä¸€ä¸ªç»™å®šçš„åœæ¢ç‚¹ (如果是NULLï¼Œå°†æ›´æ–°ä¸€è·¯æ›´æ–°åˆ°æ ‘æ ¹ï¼‰ã€‚ - 一个å¤åˆ¶å›žè°ƒï¼Œå®ƒå°†ä¸€é¢—给定åæ ‘çš„å¢žå¼ºæ•°æ®å¤åˆ¶åˆ°ä¸€ä¸ªæ–°æŒ‡å®šçš„åæ ‘æ ‘æ ¹ã€‚ - ä¸€ä¸ªæ ‘æ—‹è½¬å›žè°ƒï¼Œå®ƒå°†ä¸€é¢—ç»™å®šçš„åæ ‘çš„å¢žå¼ºå€¼å¤åˆ¶åˆ°æ–°æŒ‡å®šçš„åæ ‘æ ‘æ ¹ä¸Šï¼Œå¹¶é‡æ–°è®¡ç®— å…ˆå‰çš„åæ ‘æ ‘æ ¹çš„å¢žå¼ºå€¼ã€‚ rb_erase_augmented()编译åŽçš„代ç å¯èƒ½ä¼šå†…è”ä¼ æ’ã€å¤åˆ¶å›žè°ƒï¼Œè¿™å°†å¯¼è‡´å‡½æ•°ä½“积更大, å› æ¤æ¯ä¸ªå¢žå¼ºåž‹çº¢é»‘æ ‘çš„ç”¨æˆ·åº”è¯¥åªæœ‰ä¸€ä¸ªrb_erase_augmented()的调用点,以é™åˆ¶ç¼–è¯‘åŽ çš„ä»£ç 大å°ã€‚ 使用示例 ^^^^^^^^ åŒºé—´æ ‘æ˜¯å¢žå¼ºåž‹çº¢é»‘æ ‘çš„ä¸€ä¸ªä¾‹å。å‚考Cormen,Leiserson,Rivestå’ŒStein写的 ã€Šç®—æ³•å¯¼è®ºã€‹ã€‚åŒºé—´æ ‘çš„æ›´å¤šç»†èŠ‚ï¼š ç»å…¸çš„çº¢é»‘æ ‘åªæœ‰ä¸€ä¸ªé”®ï¼Œå®ƒä¸èƒ½ç›´æŽ¥ç”¨æ¥å˜å‚¨åƒ[lo:hi]è¿™æ ·çš„åŒºé—´èŒƒå›´ï¼Œä¹Ÿä¸èƒ½å¿«é€ŸæŸ¥æ‰¾ 与新的lo:hié‡å 的部分,或者查找是å¦æœ‰ä¸Žæ–°çš„lo:hi完全匹é…的部分。 ç„¶è€Œï¼Œçº¢é»‘æ ‘å¯ä»¥è¢«å¢žå¼ºï¼Œä»¥ä¸€ç§ç»“构化的方å¼æ¥å˜å‚¨è¿™ç§åŒºé—´èŒƒå›´ï¼Œä»Žè€Œä½¿é«˜æ•ˆçš„查找和 精确匹é…æˆä¸ºå¯èƒ½ã€‚ 这个å˜å‚¨åœ¨æ¯ä¸ªèŠ‚点ä¸çš„“é¢å¤–ä¿¡æ¯â€æ˜¯å…¶æ‰€æœ‰åŽä»£ç»“点ä¸çš„最大hi(max_hiï¼‰å€¼ã€‚è¿™ä¸ªä¿¡æ¯ å¯ä»¥ä¿æŒåœ¨æ¯ä¸ªç»“点上,åªéœ€æŸ¥çœ‹ä¸€ä¸‹è¯¥ç»“点和它的直系å结点们。这将被用于时间å¤æ‚度 为O(log n)的最低匹é…查找(所有å¯èƒ½çš„匹é…ä¸æœ€ä½Žçš„起始地å€ï¼‰ï¼Œå°±åƒè¿™æ ·:: struct interval_tree_node * interval_tree_first_match(struct rb_root *root, unsigned long start, unsigned long last) { struct interval_tree_node *node; if (!root->rb_node) return NULL; node = rb_entry(root->rb_node, struct interval_tree_node, rb); while (true) { if (node->rb.rb_left) { struct interval_tree_node *left = rb_entry(node->rb.rb_left, struct interval_tree_node, rb); if (left->__subtree_last >= start) { /* * Some nodes in left subtree satisfy Cond2. * Iterate to find the leftmost such node N. * If it also satisfies Cond1, that's the match * we are looking for. Otherwise, there is no * matching interval as nodes to the right of N * can't satisfy Cond1 either. */ node = left; continue; } } if (node->start <= last) { /* Cond1 */ if (node->last >= start) /* Cond2 */ return node; /* node is leftmost match */ if (node->rb.rb_right) { node = rb_entry(node->rb.rb_right, struct interval_tree_node, rb); if (node->__subtree_last >= start) continue; } } return NULL; /* No match */ } } æ’å…¥/åˆ é™¤æ˜¯é€šè¿‡ä»¥ä¸‹å¢žå¼ºåž‹å›žè°ƒæ¥å®šä¹‰çš„:: static inline unsigned long compute_subtree_last(struct interval_tree_node *node) { unsigned long max = node->last, subtree_last; if (node->rb.rb_left) { subtree_last = rb_entry(node->rb.rb_left, struct interval_tree_node, rb)->__subtree_last; if (max < subtree_last) max = subtree_last; } if (node->rb.rb_right) { subtree_last = rb_entry(node->rb.rb_right, struct interval_tree_node, rb)->__subtree_last; if (max < subtree_last) max = subtree_last; } return max; } static void augment_propagate(struct rb_node *rb, struct rb_node *stop) { while (rb != stop) { struct interval_tree_node *node = rb_entry(rb, struct interval_tree_node, rb); unsigned long subtree_last = compute_subtree_last(node); if (node->__subtree_last == subtree_last) break; node->__subtree_last = subtree_last; rb = rb_parent(&node->rb); } } static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) { struct interval_tree_node *old = rb_entry(rb_old, struct interval_tree_node, rb); struct interval_tree_node *new = rb_entry(rb_new, struct interval_tree_node, rb); new->__subtree_last = old->__subtree_last; } static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) { struct interval_tree_node *old = rb_entry(rb_old, struct interval_tree_node, rb); struct interval_tree_node *new = rb_entry(rb_new, struct interval_tree_node, rb); new->__subtree_last = old->__subtree_last; old->__subtree_last = compute_subtree_last(old); } static const struct rb_augment_callbacks augment_callbacks = { augment_propagate, augment_copy, augment_rotate }; void interval_tree_insert(struct interval_tree_node *node, struct rb_root *root) { struct rb_node **link = &root->rb_node, *rb_parent = NULL; unsigned long start = node->start, last = node->last; struct interval_tree_node *parent; while (*link) { rb_parent = *link; parent = rb_entry(rb_parent, struct interval_tree_node, rb); if (parent->__subtree_last < last) parent->__subtree_last = last; if (start < parent->start) link = &parent->rb.rb_left; else link = &parent->rb.rb_right; } node->__subtree_last = last; rb_link_node(&node->rb, rb_parent, link); rb_insert_augmented(&node->rb, root, &augment_callbacks); } void interval_tree_remove(struct interval_tree_node *node, struct rb_root *root) { rb_erase_augmented(&node->rb, root, &augment_callbacks); }