Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame^] | 1 | #include "drbd_interval.h" |
| 2 | |
| 3 | /** |
| 4 | * interval_end - return end of @node |
| 5 | */ |
| 6 | static inline |
| 7 | sector_t interval_end(struct rb_node *node) |
| 8 | { |
| 9 | struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb); |
| 10 | return this->end; |
| 11 | } |
| 12 | |
| 13 | /** |
| 14 | * update_interval_end - recompute end of @node |
| 15 | * |
| 16 | * The end of an interval is the highest (start + (size >> 9)) value of this |
| 17 | * node and of its children. Called for @node and its parents whenever the end |
| 18 | * may have changed. |
| 19 | */ |
| 20 | static void |
| 21 | update_interval_end(struct rb_node *node, void *__unused) |
| 22 | { |
| 23 | struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb); |
| 24 | sector_t end; |
| 25 | |
| 26 | end = this->sector + (this->size >> 9); |
| 27 | if (node->rb_left) { |
| 28 | sector_t left = interval_end(node->rb_left); |
| 29 | if (left > end) |
| 30 | end = left; |
| 31 | } |
| 32 | if (node->rb_right) { |
| 33 | sector_t right = interval_end(node->rb_right); |
| 34 | if (right > end) |
| 35 | end = right; |
| 36 | } |
| 37 | this->end = end; |
| 38 | } |
| 39 | |
| 40 | /** |
| 41 | * drbd_insert_interval - insert a new interval into a tree |
| 42 | */ |
| 43 | bool |
| 44 | drbd_insert_interval(struct rb_root *root, struct drbd_interval *this) |
| 45 | { |
| 46 | struct rb_node **new = &root->rb_node, *parent = NULL; |
| 47 | |
| 48 | BUG_ON(!IS_ALIGNED(this->size, 512)); |
| 49 | |
| 50 | while (*new) { |
| 51 | struct drbd_interval *here = |
| 52 | rb_entry(*new, struct drbd_interval, rb); |
| 53 | |
| 54 | parent = *new; |
| 55 | if (this->sector < here->sector) |
| 56 | new = &(*new)->rb_left; |
| 57 | else if (this->sector > here->sector) |
| 58 | new = &(*new)->rb_right; |
| 59 | else if (this < here) |
| 60 | new = &(*new)->rb_left; |
| 61 | else if (this->sector > here->sector) |
| 62 | new = &(*new)->rb_right; |
| 63 | return false; |
| 64 | } |
| 65 | |
| 66 | rb_link_node(&this->rb, parent, new); |
| 67 | rb_insert_color(&this->rb, root); |
| 68 | rb_augment_insert(&this->rb, update_interval_end, NULL); |
| 69 | return true; |
| 70 | } |
| 71 | |
| 72 | /** |
| 73 | * drbd_contains_interval - check if a tree contains a given interval |
| 74 | * @sector: start sector of @interval |
| 75 | * @interval: may not be a valid pointer |
| 76 | * |
| 77 | * Returns if the tree contains the node @interval with start sector @start. |
| 78 | * Does not dereference @interval until @interval is known to be a valid object |
| 79 | * in @tree. Returns %false if @interval is in the tree but with a different |
| 80 | * sector number. |
| 81 | */ |
| 82 | bool |
| 83 | drbd_contains_interval(struct rb_root *root, sector_t sector, |
| 84 | struct drbd_interval *interval) |
| 85 | { |
| 86 | struct rb_node *node = root->rb_node; |
| 87 | |
| 88 | while (node) { |
| 89 | struct drbd_interval *here = |
| 90 | rb_entry(node, struct drbd_interval, rb); |
| 91 | |
| 92 | if (sector < here->sector) |
| 93 | node = node->rb_left; |
| 94 | else if (sector > here->sector) |
| 95 | node = node->rb_right; |
| 96 | else if (interval < here) |
| 97 | node = node->rb_left; |
| 98 | else if (interval > here) |
| 99 | node = node->rb_right; |
| 100 | else |
| 101 | return interval->sector == sector; |
| 102 | } |
| 103 | return false; |
| 104 | } |
| 105 | |
| 106 | /** |
| 107 | * drbd_remove_interval - remove an interval from a tree |
| 108 | */ |
| 109 | void |
| 110 | drbd_remove_interval(struct rb_root *root, struct drbd_interval *this) |
| 111 | { |
| 112 | struct rb_node *deepest; |
| 113 | |
| 114 | deepest = rb_augment_erase_begin(&this->rb); |
| 115 | rb_erase(&this->rb, root); |
| 116 | rb_augment_erase_end(deepest, update_interval_end, NULL); |
| 117 | } |
| 118 | |
| 119 | /** |
| 120 | * drbd_find_overlap - search for an interval overlapping with [sector, sector + size) |
| 121 | * @sector: start sector |
| 122 | * @size: size, aligned to 512 bytes |
| 123 | * |
| 124 | * Returns the interval overlapping with [sector, sector + size), or NULL. |
| 125 | * When there is more than one overlapping interval in the tree, the interval |
| 126 | * with the lowest start sector is returned. |
| 127 | */ |
| 128 | struct drbd_interval * |
| 129 | drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size) |
| 130 | { |
| 131 | struct rb_node *node = root->rb_node; |
| 132 | struct drbd_interval *overlap = NULL; |
| 133 | sector_t end = sector + (size >> 9); |
| 134 | |
| 135 | BUG_ON(!IS_ALIGNED(size, 512)); |
| 136 | |
| 137 | while (node) { |
| 138 | struct drbd_interval *here = |
| 139 | rb_entry(node, struct drbd_interval, rb); |
| 140 | |
| 141 | if (node->rb_left && |
| 142 | sector < interval_end(node->rb_left)) { |
| 143 | /* Overlap if any must be on left side */ |
| 144 | node = node->rb_left; |
| 145 | } else if (here->sector < end && |
| 146 | sector < here->sector + (here->size >> 9)) { |
| 147 | overlap = here; |
| 148 | break; |
| 149 | } else if (sector >= here->sector) { |
| 150 | /* Overlap if any must be on right side */ |
| 151 | node = node->rb_right; |
| 152 | } else |
| 153 | break; |
| 154 | } |
| 155 | return overlap; |
| 156 | } |