10939b0e5SAndreas Gruenbacher #include "drbd_interval.h" 20939b0e5SAndreas Gruenbacher 30939b0e5SAndreas Gruenbacher /** 40939b0e5SAndreas Gruenbacher * interval_end - return end of @node 50939b0e5SAndreas Gruenbacher */ 60939b0e5SAndreas Gruenbacher static inline 70939b0e5SAndreas Gruenbacher sector_t interval_end(struct rb_node *node) 80939b0e5SAndreas Gruenbacher { 90939b0e5SAndreas Gruenbacher struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb); 100939b0e5SAndreas Gruenbacher return this->end; 110939b0e5SAndreas Gruenbacher } 120939b0e5SAndreas Gruenbacher 130939b0e5SAndreas Gruenbacher /** 140939b0e5SAndreas Gruenbacher * update_interval_end - recompute end of @node 150939b0e5SAndreas Gruenbacher * 160939b0e5SAndreas Gruenbacher * The end of an interval is the highest (start + (size >> 9)) value of this 170939b0e5SAndreas Gruenbacher * node and of its children. Called for @node and its parents whenever the end 180939b0e5SAndreas Gruenbacher * may have changed. 190939b0e5SAndreas Gruenbacher */ 200939b0e5SAndreas Gruenbacher static void 210939b0e5SAndreas Gruenbacher update_interval_end(struct rb_node *node, void *__unused) 220939b0e5SAndreas Gruenbacher { 230939b0e5SAndreas Gruenbacher struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb); 240939b0e5SAndreas Gruenbacher sector_t end; 250939b0e5SAndreas Gruenbacher 260939b0e5SAndreas Gruenbacher end = this->sector + (this->size >> 9); 270939b0e5SAndreas Gruenbacher if (node->rb_left) { 280939b0e5SAndreas Gruenbacher sector_t left = interval_end(node->rb_left); 290939b0e5SAndreas Gruenbacher if (left > end) 300939b0e5SAndreas Gruenbacher end = left; 310939b0e5SAndreas Gruenbacher } 320939b0e5SAndreas Gruenbacher if (node->rb_right) { 330939b0e5SAndreas Gruenbacher sector_t right = interval_end(node->rb_right); 340939b0e5SAndreas Gruenbacher if (right > end) 350939b0e5SAndreas Gruenbacher end = right; 360939b0e5SAndreas Gruenbacher } 370939b0e5SAndreas Gruenbacher this->end = end; 380939b0e5SAndreas Gruenbacher } 390939b0e5SAndreas Gruenbacher 400939b0e5SAndreas Gruenbacher /** 410939b0e5SAndreas Gruenbacher * drbd_insert_interval - insert a new interval into a tree 420939b0e5SAndreas Gruenbacher */ 430939b0e5SAndreas Gruenbacher bool 440939b0e5SAndreas Gruenbacher drbd_insert_interval(struct rb_root *root, struct drbd_interval *this) 450939b0e5SAndreas Gruenbacher { 460939b0e5SAndreas Gruenbacher struct rb_node **new = &root->rb_node, *parent = NULL; 470939b0e5SAndreas Gruenbacher 480939b0e5SAndreas Gruenbacher BUG_ON(!IS_ALIGNED(this->size, 512)); 490939b0e5SAndreas Gruenbacher 500939b0e5SAndreas Gruenbacher while (*new) { 510939b0e5SAndreas Gruenbacher struct drbd_interval *here = 520939b0e5SAndreas Gruenbacher rb_entry(*new, struct drbd_interval, rb); 530939b0e5SAndreas Gruenbacher 540939b0e5SAndreas Gruenbacher parent = *new; 550939b0e5SAndreas Gruenbacher if (this->sector < here->sector) 560939b0e5SAndreas Gruenbacher new = &(*new)->rb_left; 570939b0e5SAndreas Gruenbacher else if (this->sector > here->sector) 580939b0e5SAndreas Gruenbacher new = &(*new)->rb_right; 590939b0e5SAndreas Gruenbacher else if (this < here) 600939b0e5SAndreas Gruenbacher new = &(*new)->rb_left; 610939b0e5SAndreas Gruenbacher else if (this->sector > here->sector) 620939b0e5SAndreas Gruenbacher new = &(*new)->rb_right; 630939b0e5SAndreas Gruenbacher return false; 640939b0e5SAndreas Gruenbacher } 650939b0e5SAndreas Gruenbacher 660939b0e5SAndreas Gruenbacher rb_link_node(&this->rb, parent, new); 670939b0e5SAndreas Gruenbacher rb_insert_color(&this->rb, root); 680939b0e5SAndreas Gruenbacher rb_augment_insert(&this->rb, update_interval_end, NULL); 690939b0e5SAndreas Gruenbacher return true; 700939b0e5SAndreas Gruenbacher } 710939b0e5SAndreas Gruenbacher 720939b0e5SAndreas Gruenbacher /** 730939b0e5SAndreas Gruenbacher * drbd_contains_interval - check if a tree contains a given interval 740939b0e5SAndreas Gruenbacher * @sector: start sector of @interval 750939b0e5SAndreas Gruenbacher * @interval: may not be a valid pointer 760939b0e5SAndreas Gruenbacher * 770939b0e5SAndreas Gruenbacher * Returns if the tree contains the node @interval with start sector @start. 780939b0e5SAndreas Gruenbacher * Does not dereference @interval until @interval is known to be a valid object 790939b0e5SAndreas Gruenbacher * in @tree. Returns %false if @interval is in the tree but with a different 800939b0e5SAndreas Gruenbacher * sector number. 810939b0e5SAndreas Gruenbacher */ 820939b0e5SAndreas Gruenbacher bool 830939b0e5SAndreas Gruenbacher drbd_contains_interval(struct rb_root *root, sector_t sector, 840939b0e5SAndreas Gruenbacher struct drbd_interval *interval) 850939b0e5SAndreas Gruenbacher { 860939b0e5SAndreas Gruenbacher struct rb_node *node = root->rb_node; 870939b0e5SAndreas Gruenbacher 880939b0e5SAndreas Gruenbacher while (node) { 890939b0e5SAndreas Gruenbacher struct drbd_interval *here = 900939b0e5SAndreas Gruenbacher rb_entry(node, struct drbd_interval, rb); 910939b0e5SAndreas Gruenbacher 920939b0e5SAndreas Gruenbacher if (sector < here->sector) 930939b0e5SAndreas Gruenbacher node = node->rb_left; 940939b0e5SAndreas Gruenbacher else if (sector > here->sector) 950939b0e5SAndreas Gruenbacher node = node->rb_right; 960939b0e5SAndreas Gruenbacher else if (interval < here) 970939b0e5SAndreas Gruenbacher node = node->rb_left; 980939b0e5SAndreas Gruenbacher else if (interval > here) 990939b0e5SAndreas Gruenbacher node = node->rb_right; 1000939b0e5SAndreas Gruenbacher else 1010939b0e5SAndreas Gruenbacher return interval->sector == sector; 1020939b0e5SAndreas Gruenbacher } 1030939b0e5SAndreas Gruenbacher return false; 1040939b0e5SAndreas Gruenbacher } 1050939b0e5SAndreas Gruenbacher 1060939b0e5SAndreas Gruenbacher /** 1070939b0e5SAndreas Gruenbacher * drbd_remove_interval - remove an interval from a tree 1080939b0e5SAndreas Gruenbacher */ 1090939b0e5SAndreas Gruenbacher void 1100939b0e5SAndreas Gruenbacher drbd_remove_interval(struct rb_root *root, struct drbd_interval *this) 1110939b0e5SAndreas Gruenbacher { 1120939b0e5SAndreas Gruenbacher struct rb_node *deepest; 1130939b0e5SAndreas Gruenbacher 1140939b0e5SAndreas Gruenbacher deepest = rb_augment_erase_begin(&this->rb); 1150939b0e5SAndreas Gruenbacher rb_erase(&this->rb, root); 1160939b0e5SAndreas Gruenbacher rb_augment_erase_end(deepest, update_interval_end, NULL); 1170939b0e5SAndreas Gruenbacher } 1180939b0e5SAndreas Gruenbacher 1190939b0e5SAndreas Gruenbacher /** 1200939b0e5SAndreas Gruenbacher * drbd_find_overlap - search for an interval overlapping with [sector, sector + size) 1210939b0e5SAndreas Gruenbacher * @sector: start sector 1220939b0e5SAndreas Gruenbacher * @size: size, aligned to 512 bytes 1230939b0e5SAndreas Gruenbacher * 1240939b0e5SAndreas Gruenbacher * Returns the interval overlapping with [sector, sector + size), or NULL. 1250939b0e5SAndreas Gruenbacher * When there is more than one overlapping interval in the tree, the interval 1260939b0e5SAndreas Gruenbacher * with the lowest start sector is returned. 1270939b0e5SAndreas Gruenbacher */ 1280939b0e5SAndreas Gruenbacher struct drbd_interval * 1290939b0e5SAndreas Gruenbacher drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size) 1300939b0e5SAndreas Gruenbacher { 1310939b0e5SAndreas Gruenbacher struct rb_node *node = root->rb_node; 1320939b0e5SAndreas Gruenbacher struct drbd_interval *overlap = NULL; 1330939b0e5SAndreas Gruenbacher sector_t end = sector + (size >> 9); 1340939b0e5SAndreas Gruenbacher 1350939b0e5SAndreas Gruenbacher BUG_ON(!IS_ALIGNED(size, 512)); 1360939b0e5SAndreas Gruenbacher 1370939b0e5SAndreas Gruenbacher while (node) { 1380939b0e5SAndreas Gruenbacher struct drbd_interval *here = 1390939b0e5SAndreas Gruenbacher rb_entry(node, struct drbd_interval, rb); 1400939b0e5SAndreas Gruenbacher 1410939b0e5SAndreas Gruenbacher if (node->rb_left && 1420939b0e5SAndreas Gruenbacher sector < interval_end(node->rb_left)) { 1430939b0e5SAndreas Gruenbacher /* Overlap if any must be on left side */ 1440939b0e5SAndreas Gruenbacher node = node->rb_left; 1450939b0e5SAndreas Gruenbacher } else if (here->sector < end && 1460939b0e5SAndreas Gruenbacher sector < here->sector + (here->size >> 9)) { 1470939b0e5SAndreas Gruenbacher overlap = here; 1480939b0e5SAndreas Gruenbacher break; 1490939b0e5SAndreas Gruenbacher } else if (sector >= here->sector) { 1500939b0e5SAndreas Gruenbacher /* Overlap if any must be on right side */ 1510939b0e5SAndreas Gruenbacher node = node->rb_right; 1520939b0e5SAndreas Gruenbacher } else 1530939b0e5SAndreas Gruenbacher break; 1540939b0e5SAndreas Gruenbacher } 1550939b0e5SAndreas Gruenbacher return overlap; 1560939b0e5SAndreas Gruenbacher } 157