1*93c68cc4SChristoph Böhmwalder // SPDX-License-Identifier: GPL-2.0-only 298683650SPhilipp Reisner #include <asm/bug.h> 398683650SPhilipp Reisner #include <linux/rbtree_augmented.h> 40939b0e5SAndreas Gruenbacher #include "drbd_interval.h" 50939b0e5SAndreas Gruenbacher 6b8b87103SLee Jones /* 70939b0e5SAndreas Gruenbacher * interval_end - return end of @node 80939b0e5SAndreas Gruenbacher */ 90939b0e5SAndreas Gruenbacher static inline 100939b0e5SAndreas Gruenbacher sector_t interval_end(struct rb_node *node) 110939b0e5SAndreas Gruenbacher { 120939b0e5SAndreas Gruenbacher struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb); 130939b0e5SAndreas Gruenbacher return this->end; 140939b0e5SAndreas Gruenbacher } 150939b0e5SAndreas Gruenbacher 16315cc066SMichel Lespinasse #define NODE_END(node) ((node)->sector + ((node)->size >> 9)) 170939b0e5SAndreas Gruenbacher 18315cc066SMichel Lespinasse RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks, 19315cc066SMichel Lespinasse struct drbd_interval, rb, sector_t, end, NODE_END); 2098683650SPhilipp Reisner 21b8b87103SLee Jones /* 220939b0e5SAndreas Gruenbacher * drbd_insert_interval - insert a new interval into a tree 230939b0e5SAndreas Gruenbacher */ 240939b0e5SAndreas Gruenbacher bool 250939b0e5SAndreas Gruenbacher drbd_insert_interval(struct rb_root *root, struct drbd_interval *this) 260939b0e5SAndreas Gruenbacher { 270939b0e5SAndreas Gruenbacher struct rb_node **new = &root->rb_node, *parent = NULL; 2882cfb90bSLai Jiangshan sector_t this_end = this->sector + (this->size >> 9); 290939b0e5SAndreas Gruenbacher 300939b0e5SAndreas Gruenbacher BUG_ON(!IS_ALIGNED(this->size, 512)); 310939b0e5SAndreas Gruenbacher 320939b0e5SAndreas Gruenbacher while (*new) { 330939b0e5SAndreas Gruenbacher struct drbd_interval *here = 340939b0e5SAndreas Gruenbacher rb_entry(*new, struct drbd_interval, rb); 350939b0e5SAndreas Gruenbacher 360939b0e5SAndreas Gruenbacher parent = *new; 3782cfb90bSLai Jiangshan if (here->end < this_end) 3882cfb90bSLai Jiangshan here->end = this_end; 390939b0e5SAndreas Gruenbacher if (this->sector < here->sector) 400939b0e5SAndreas Gruenbacher new = &(*new)->rb_left; 410939b0e5SAndreas Gruenbacher else if (this->sector > here->sector) 420939b0e5SAndreas Gruenbacher new = &(*new)->rb_right; 430939b0e5SAndreas Gruenbacher else if (this < here) 440939b0e5SAndreas Gruenbacher new = &(*new)->rb_left; 456618bf16SAndreas Gruenbacher else if (this > here) 460939b0e5SAndreas Gruenbacher new = &(*new)->rb_right; 476618bf16SAndreas Gruenbacher else 480939b0e5SAndreas Gruenbacher return false; 490939b0e5SAndreas Gruenbacher } 500939b0e5SAndreas Gruenbacher 5182cfb90bSLai Jiangshan this->end = this_end; 520939b0e5SAndreas Gruenbacher rb_link_node(&this->rb, parent, new); 5398683650SPhilipp Reisner rb_insert_augmented(&this->rb, root, &augment_callbacks); 540939b0e5SAndreas Gruenbacher return true; 550939b0e5SAndreas Gruenbacher } 560939b0e5SAndreas Gruenbacher 570939b0e5SAndreas Gruenbacher /** 580939b0e5SAndreas Gruenbacher * drbd_contains_interval - check if a tree contains a given interval 59b8b87103SLee Jones * @root: red black tree root 600939b0e5SAndreas Gruenbacher * @sector: start sector of @interval 610939b0e5SAndreas Gruenbacher * @interval: may not be a valid pointer 620939b0e5SAndreas Gruenbacher * 630939b0e5SAndreas Gruenbacher * Returns if the tree contains the node @interval with start sector @start. 640939b0e5SAndreas Gruenbacher * Does not dereference @interval until @interval is known to be a valid object 650939b0e5SAndreas Gruenbacher * in @tree. Returns %false if @interval is in the tree but with a different 660939b0e5SAndreas Gruenbacher * sector number. 670939b0e5SAndreas Gruenbacher */ 680939b0e5SAndreas Gruenbacher bool 690939b0e5SAndreas Gruenbacher drbd_contains_interval(struct rb_root *root, sector_t sector, 700939b0e5SAndreas Gruenbacher struct drbd_interval *interval) 710939b0e5SAndreas Gruenbacher { 720939b0e5SAndreas Gruenbacher struct rb_node *node = root->rb_node; 730939b0e5SAndreas Gruenbacher 740939b0e5SAndreas Gruenbacher while (node) { 750939b0e5SAndreas Gruenbacher struct drbd_interval *here = 760939b0e5SAndreas Gruenbacher rb_entry(node, struct drbd_interval, rb); 770939b0e5SAndreas Gruenbacher 780939b0e5SAndreas Gruenbacher if (sector < here->sector) 790939b0e5SAndreas Gruenbacher node = node->rb_left; 800939b0e5SAndreas Gruenbacher else if (sector > here->sector) 810939b0e5SAndreas Gruenbacher node = node->rb_right; 820939b0e5SAndreas Gruenbacher else if (interval < here) 830939b0e5SAndreas Gruenbacher node = node->rb_left; 840939b0e5SAndreas Gruenbacher else if (interval > here) 850939b0e5SAndreas Gruenbacher node = node->rb_right; 860939b0e5SAndreas Gruenbacher else 873e05146fSAndreas Gruenbacher return true; 880939b0e5SAndreas Gruenbacher } 890939b0e5SAndreas Gruenbacher return false; 900939b0e5SAndreas Gruenbacher } 910939b0e5SAndreas Gruenbacher 92b8b87103SLee Jones /* 930939b0e5SAndreas Gruenbacher * drbd_remove_interval - remove an interval from a tree 940939b0e5SAndreas Gruenbacher */ 950939b0e5SAndreas Gruenbacher void 960939b0e5SAndreas Gruenbacher drbd_remove_interval(struct rb_root *root, struct drbd_interval *this) 970939b0e5SAndreas Gruenbacher { 9898683650SPhilipp Reisner rb_erase_augmented(&this->rb, root, &augment_callbacks); 990939b0e5SAndreas Gruenbacher } 1000939b0e5SAndreas Gruenbacher 1010939b0e5SAndreas Gruenbacher /** 1020939b0e5SAndreas Gruenbacher * drbd_find_overlap - search for an interval overlapping with [sector, sector + size) 103b8b87103SLee Jones * @root: red black tree root 1040939b0e5SAndreas Gruenbacher * @sector: start sector 1050939b0e5SAndreas Gruenbacher * @size: size, aligned to 512 bytes 1060939b0e5SAndreas Gruenbacher * 10770b19876SAndreas Gruenbacher * Returns an interval overlapping with [sector, sector + size), or NULL if 10870b19876SAndreas Gruenbacher * there is none. When there is more than one overlapping interval in the 10970b19876SAndreas Gruenbacher * tree, the interval with the lowest start sector is returned, and all other 11070b19876SAndreas Gruenbacher * overlapping intervals will be on the right side of the tree, reachable with 11170b19876SAndreas Gruenbacher * rb_next(). 1120939b0e5SAndreas Gruenbacher */ 1130939b0e5SAndreas Gruenbacher struct drbd_interval * 1140939b0e5SAndreas Gruenbacher drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size) 1150939b0e5SAndreas Gruenbacher { 1160939b0e5SAndreas Gruenbacher struct rb_node *node = root->rb_node; 1170939b0e5SAndreas Gruenbacher struct drbd_interval *overlap = NULL; 1180939b0e5SAndreas Gruenbacher sector_t end = sector + (size >> 9); 1190939b0e5SAndreas Gruenbacher 1200939b0e5SAndreas Gruenbacher BUG_ON(!IS_ALIGNED(size, 512)); 1210939b0e5SAndreas Gruenbacher 1220939b0e5SAndreas Gruenbacher while (node) { 1230939b0e5SAndreas Gruenbacher struct drbd_interval *here = 1240939b0e5SAndreas Gruenbacher rb_entry(node, struct drbd_interval, rb); 1250939b0e5SAndreas Gruenbacher 1260939b0e5SAndreas Gruenbacher if (node->rb_left && 1270939b0e5SAndreas Gruenbacher sector < interval_end(node->rb_left)) { 1280939b0e5SAndreas Gruenbacher /* Overlap if any must be on left side */ 1290939b0e5SAndreas Gruenbacher node = node->rb_left; 1300939b0e5SAndreas Gruenbacher } else if (here->sector < end && 1310939b0e5SAndreas Gruenbacher sector < here->sector + (here->size >> 9)) { 1320939b0e5SAndreas Gruenbacher overlap = here; 1330939b0e5SAndreas Gruenbacher break; 1340939b0e5SAndreas Gruenbacher } else if (sector >= here->sector) { 1350939b0e5SAndreas Gruenbacher /* Overlap if any must be on right side */ 1360939b0e5SAndreas Gruenbacher node = node->rb_right; 1370939b0e5SAndreas Gruenbacher } else 1380939b0e5SAndreas Gruenbacher break; 1390939b0e5SAndreas Gruenbacher } 1400939b0e5SAndreas Gruenbacher return overlap; 1410939b0e5SAndreas Gruenbacher } 142d0e22a26SAndreas Gruenbacher 143d0e22a26SAndreas Gruenbacher struct drbd_interval * 144d0e22a26SAndreas Gruenbacher drbd_next_overlap(struct drbd_interval *i, sector_t sector, unsigned int size) 145d0e22a26SAndreas Gruenbacher { 146d0e22a26SAndreas Gruenbacher sector_t end = sector + (size >> 9); 147d0e22a26SAndreas Gruenbacher struct rb_node *node; 148d0e22a26SAndreas Gruenbacher 149d0e22a26SAndreas Gruenbacher for (;;) { 150d0e22a26SAndreas Gruenbacher node = rb_next(&i->rb); 151d0e22a26SAndreas Gruenbacher if (!node) 152d0e22a26SAndreas Gruenbacher return NULL; 153d0e22a26SAndreas Gruenbacher i = rb_entry(node, struct drbd_interval, rb); 154d0e22a26SAndreas Gruenbacher if (i->sector >= end) 155d0e22a26SAndreas Gruenbacher return NULL; 156d0e22a26SAndreas Gruenbacher if (sector < i->sector + (i->size >> 9)) 157d0e22a26SAndreas Gruenbacher return i; 158d0e22a26SAndreas Gruenbacher } 159d0e22a26SAndreas Gruenbacher } 160