diff options
author | Andreas Gruenbacher <agruen@linbit.com> | 2011-01-03 17:42:00 +0100 |
---|---|---|
committer | Philipp Reisner <philipp.reisner@linbit.com> | 2011-08-25 14:58:04 +0200 |
commit | 0939b0e5cdeeafa0adf0150edd350092e47acc49 (patch) | |
tree | 8efaf1d9aadf77b76ca66b4968bce89cb78a6b98 /drivers/block/drbd/drbd_interval.h | |
parent | c3afd8f568999e974382f7b5b05267c018056016 (diff) | |
download | linux-stable-0939b0e5cdeeafa0adf0150edd350092e47acc49.tar.gz linux-stable-0939b0e5cdeeafa0adf0150edd350092e47acc49.tar.bz2 linux-stable-0939b0e5cdeeafa0adf0150edd350092e47acc49.zip |
drbd: Add interval tree data structure
Signed-off-by: Philipp Reisner <philipp.reisner@linbit.com>
Signed-off-by: Lars Ellenberg <lars.ellenberg@linbit.com>
Diffstat (limited to 'drivers/block/drbd/drbd_interval.h')
-rw-r--r-- | drivers/block/drbd/drbd_interval.h | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/drivers/block/drbd/drbd_interval.h b/drivers/block/drbd/drbd_interval.h new file mode 100644 index 000000000000..bf8dcf7bab09 --- /dev/null +++ b/drivers/block/drbd/drbd_interval.h @@ -0,0 +1,31 @@ +#ifndef __DRBD_INTERVAL_H +#define __DRBD_INTERVAL_H + +#include <linux/types.h> +#include <linux/rbtree.h> + +struct drbd_interval { + struct rb_node rb; + sector_t sector; /* start sector of the interval */ + unsigned int size; /* size in bytes */ + sector_t end; /* highest interval end in subtree */ +}; + +static inline void drbd_clear_interval(struct drbd_interval *i) +{ + RB_CLEAR_NODE(&i->rb); +} + +static inline bool drbd_interval_empty(struct drbd_interval *i) +{ + return RB_EMPTY_NODE(&i->rb); +} + +bool drbd_insert_interval(struct rb_root *, struct drbd_interval *); +struct drbd_interval *drbd_find_interval(struct rb_root *, sector_t, + struct drbd_interval *); +void drbd_remove_interval(struct rb_root *, struct drbd_interval *); +struct drbd_interval *drbd_find_overlap(struct rb_root *, sector_t, + unsigned int); + +#endif /* __DRBD_INTERVAL_H */ |