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; 616618bf16SAndreas Gruenbacher else if (this > here) 620939b0e5SAndreas Gruenbacher new = &(*new)->rb_right; 636618bf16SAndreas Gruenbacher else 640939b0e5SAndreas Gruenbacher return false; 650939b0e5SAndreas Gruenbacher } 660939b0e5SAndreas Gruenbacher 670939b0e5SAndreas Gruenbacher rb_link_node(&this->rb, parent, new); 680939b0e5SAndreas Gruenbacher rb_insert_color(&this->rb, root); 690939b0e5SAndreas Gruenbacher rb_augment_insert(&this->rb, update_interval_end, NULL); 700939b0e5SAndreas Gruenbacher return true; 710939b0e5SAndreas Gruenbacher } 720939b0e5SAndreas Gruenbacher 730939b0e5SAndreas Gruenbacher /** 740939b0e5SAndreas Gruenbacher * drbd_contains_interval - check if a tree contains a given interval 750939b0e5SAndreas Gruenbacher * @sector: start sector of @interval 760939b0e5SAndreas Gruenbacher * @interval: may not be a valid pointer 770939b0e5SAndreas Gruenbacher * 780939b0e5SAndreas Gruenbacher * Returns if the tree contains the node @interval with start sector @start. 790939b0e5SAndreas Gruenbacher * Does not dereference @interval until @interval is known to be a valid object 800939b0e5SAndreas Gruenbacher * in @tree. Returns %false if @interval is in the tree but with a different 810939b0e5SAndreas Gruenbacher * sector number. 820939b0e5SAndreas Gruenbacher */ 830939b0e5SAndreas Gruenbacher bool 840939b0e5SAndreas Gruenbacher drbd_contains_interval(struct rb_root *root, sector_t sector, 850939b0e5SAndreas Gruenbacher struct drbd_interval *interval) 860939b0e5SAndreas Gruenbacher { 870939b0e5SAndreas Gruenbacher struct rb_node *node = root->rb_node; 880939b0e5SAndreas Gruenbacher 890939b0e5SAndreas Gruenbacher while (node) { 900939b0e5SAndreas Gruenbacher struct drbd_interval *here = 910939b0e5SAndreas Gruenbacher rb_entry(node, struct drbd_interval, rb); 920939b0e5SAndreas Gruenbacher 930939b0e5SAndreas Gruenbacher if (sector < here->sector) 940939b0e5SAndreas Gruenbacher node = node->rb_left; 950939b0e5SAndreas Gruenbacher else if (sector > here->sector) 960939b0e5SAndreas Gruenbacher node = node->rb_right; 970939b0e5SAndreas Gruenbacher else if (interval < here) 980939b0e5SAndreas Gruenbacher node = node->rb_left; 990939b0e5SAndreas Gruenbacher else if (interval > here) 1000939b0e5SAndreas Gruenbacher node = node->rb_right; 1010939b0e5SAndreas Gruenbacher else 1023e05146fSAndreas Gruenbacher return true; 1030939b0e5SAndreas Gruenbacher } 1040939b0e5SAndreas Gruenbacher return false; 1050939b0e5SAndreas Gruenbacher } 1060939b0e5SAndreas Gruenbacher 1070939b0e5SAndreas Gruenbacher /** 1080939b0e5SAndreas Gruenbacher * drbd_remove_interval - remove an interval from a tree 1090939b0e5SAndreas Gruenbacher */ 1100939b0e5SAndreas Gruenbacher void 1110939b0e5SAndreas Gruenbacher drbd_remove_interval(struct rb_root *root, struct drbd_interval *this) 1120939b0e5SAndreas Gruenbacher { 1130939b0e5SAndreas Gruenbacher struct rb_node *deepest; 1140939b0e5SAndreas Gruenbacher 1150939b0e5SAndreas Gruenbacher deepest = rb_augment_erase_begin(&this->rb); 1160939b0e5SAndreas Gruenbacher rb_erase(&this->rb, root); 1170939b0e5SAndreas Gruenbacher rb_augment_erase_end(deepest, update_interval_end, NULL); 1180939b0e5SAndreas Gruenbacher } 1190939b0e5SAndreas Gruenbacher 1200939b0e5SAndreas Gruenbacher /** 1210939b0e5SAndreas Gruenbacher * drbd_find_overlap - search for an interval overlapping with [sector, sector + size) 1220939b0e5SAndreas Gruenbacher * @sector: start sector 1230939b0e5SAndreas Gruenbacher * @size: size, aligned to 512 bytes 1240939b0e5SAndreas Gruenbacher * 12570b19876SAndreas Gruenbacher * Returns an interval overlapping with [sector, sector + size), or NULL if 12670b19876SAndreas Gruenbacher * there is none. When there is more than one overlapping interval in the 12770b19876SAndreas Gruenbacher * tree, the interval with the lowest start sector is returned, and all other 12870b19876SAndreas Gruenbacher * overlapping intervals will be on the right side of the tree, reachable with 12970b19876SAndreas Gruenbacher * rb_next(). 1300939b0e5SAndreas Gruenbacher */ 1310939b0e5SAndreas Gruenbacher struct drbd_interval * 1320939b0e5SAndreas Gruenbacher drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size) 1330939b0e5SAndreas Gruenbacher { 1340939b0e5SAndreas Gruenbacher struct rb_node *node = root->rb_node; 1350939b0e5SAndreas Gruenbacher struct drbd_interval *overlap = NULL; 1360939b0e5SAndreas Gruenbacher sector_t end = sector + (size >> 9); 1370939b0e5SAndreas Gruenbacher 1380939b0e5SAndreas Gruenbacher BUG_ON(!IS_ALIGNED(size, 512)); 1390939b0e5SAndreas Gruenbacher 1400939b0e5SAndreas Gruenbacher while (node) { 1410939b0e5SAndreas Gruenbacher struct drbd_interval *here = 1420939b0e5SAndreas Gruenbacher rb_entry(node, struct drbd_interval, rb); 1430939b0e5SAndreas Gruenbacher 1440939b0e5SAndreas Gruenbacher if (node->rb_left && 1450939b0e5SAndreas Gruenbacher sector < interval_end(node->rb_left)) { 1460939b0e5SAndreas Gruenbacher /* Overlap if any must be on left side */ 1470939b0e5SAndreas Gruenbacher node = node->rb_left; 1480939b0e5SAndreas Gruenbacher } else if (here->sector < end && 1490939b0e5SAndreas Gruenbacher sector < here->sector + (here->size >> 9)) { 1500939b0e5SAndreas Gruenbacher overlap = here; 1510939b0e5SAndreas Gruenbacher break; 1520939b0e5SAndreas Gruenbacher } else if (sector >= here->sector) { 1530939b0e5SAndreas Gruenbacher /* Overlap if any must be on right side */ 1540939b0e5SAndreas Gruenbacher node = node->rb_right; 1550939b0e5SAndreas Gruenbacher } else 1560939b0e5SAndreas Gruenbacher break; 1570939b0e5SAndreas Gruenbacher } 1580939b0e5SAndreas Gruenbacher return overlap; 1590939b0e5SAndreas Gruenbacher } 160d0e22a26SAndreas Gruenbacher 161d0e22a26SAndreas Gruenbacher struct drbd_interval * 162d0e22a26SAndreas Gruenbacher drbd_next_overlap(struct drbd_interval *i, sector_t sector, unsigned int size) 163d0e22a26SAndreas Gruenbacher { 164d0e22a26SAndreas Gruenbacher sector_t end = sector + (size >> 9); 165d0e22a26SAndreas Gruenbacher struct rb_node *node; 166d0e22a26SAndreas Gruenbacher 167d0e22a26SAndreas Gruenbacher for (;;) { 168d0e22a26SAndreas Gruenbacher node = rb_next(&i->rb); 169d0e22a26SAndreas Gruenbacher if (!node) 170d0e22a26SAndreas Gruenbacher return NULL; 171d0e22a26SAndreas Gruenbacher i = rb_entry(node, struct drbd_interval, rb); 172d0e22a26SAndreas Gruenbacher if (i->sector >= end) 173d0e22a26SAndreas Gruenbacher return NULL; 174d0e22a26SAndreas Gruenbacher if (sector < i->sector + (i->size >> 9)) 175d0e22a26SAndreas Gruenbacher return i; 176d0e22a26SAndreas Gruenbacher } 177d0e22a26SAndreas Gruenbacher } 178