From: Philipp Reisner <philipp.reisner@linbit.com>
To: linux-kernel@vger.kernel.org, Jens Axboe <axboe@kernel.dk>
Cc: drbd-dev@lists.linbit.com
Subject: [PATCH 02/15] drbd: Iterate over all overlapping intervals in a tree
Date: Tue, 30 Aug 2011 11:05:36 +0200 [thread overview]
Message-ID: <1314695149-387-3-git-send-email-philipp.reisner@linbit.com> (raw)
In-Reply-To: <1314695149-387-1-git-send-email-philipp.reisner@linbit.com>
From: Andreas Gruenbacher <agruen@linbit.com>
Add a macro and helper function for doing that.
Signed-off-by: Philipp Reisner <philipp.reisner@linbit.com>
Signed-off-by: Lars Ellenberg <lars.ellenberg@linbit.com>
---
drivers/block/drbd/drbd_interval.c | 18 ++++++++++++++++++
drivers/block/drbd/drbd_interval.h | 16 ++++++++++++----
2 files changed, 30 insertions(+), 4 deletions(-)
diff --git a/drivers/block/drbd/drbd_interval.c b/drivers/block/drbd/drbd_interval.c
index 14dbe2d..0e53f10 100644
--- a/drivers/block/drbd/drbd_interval.c
+++ b/drivers/block/drbd/drbd_interval.c
@@ -157,3 +157,21 @@ drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size)
}
return overlap;
}
+
+struct drbd_interval *
+drbd_next_overlap(struct drbd_interval *i, sector_t sector, unsigned int size)
+{
+ sector_t end = sector + (size >> 9);
+ struct rb_node *node;
+
+ for (;;) {
+ node = rb_next(&i->rb);
+ if (!node)
+ return NULL;
+ i = rb_entry(node, struct drbd_interval, rb);
+ if (i->sector >= end)
+ return NULL;
+ if (sector < i->sector + (i->size >> 9))
+ return i;
+ }
+}
diff --git a/drivers/block/drbd/drbd_interval.h b/drivers/block/drbd/drbd_interval.h
index 4010ad9..f38fcb0 100644
--- a/drivers/block/drbd/drbd_interval.h
+++ b/drivers/block/drbd/drbd_interval.h
@@ -23,10 +23,18 @@ 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 *);
-bool drbd_contains_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,
+extern bool drbd_insert_interval(struct rb_root *, struct drbd_interval *);
+extern bool drbd_contains_interval(struct rb_root *, sector_t,
+ struct drbd_interval *);
+extern void drbd_remove_interval(struct rb_root *, struct drbd_interval *);
+extern struct drbd_interval *drbd_find_overlap(struct rb_root *, sector_t,
unsigned int);
+extern struct drbd_interval *drbd_next_overlap(struct drbd_interval *, sector_t,
+ unsigned int);
+
+#define drbd_for_each_overlap(i, root, sector, size) \
+ for (i = drbd_find_overlap(root, sector, size); \
+ i; \
+ i = drbd_next_overlap(i, sector, size))
#endif /* __DRBD_INTERVAL_H */
--
1.7.4.1
next prev parent reply other threads:[~2011-08-30 9:05 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-08-30 9:05 [RFC 00/15] drbd: part 2 of adding multiple volume support to drbd Philipp Reisner
2011-08-30 9:05 ` [PATCH 01/15] drbd: Rename drbd_endio_{pri,sec} -> drbd_{,peer_}request_endio Philipp Reisner
2011-08-30 9:05 ` Philipp Reisner [this message]
2011-08-30 9:05 ` [PATCH 03/15] drbd: Remove obsolete comment Philipp Reisner
2011-08-30 9:05 ` [PATCH 04/15] drbd: Use the IS_ALIGNED() macro in some more places Philipp Reisner
2011-08-30 9:05 ` [PATCH 05/15] drbd: simplify condition in drbd_may_do_local_read() Philipp Reisner
2011-08-30 9:05 ` [PATCH 06/15] drbd: fix typo in comment Philipp Reisner
2011-08-30 9:05 ` [PATCH 07/15] drbd: in drbd_suspend_al, set AL_SUSPENDED before unlocking the activity log Philipp Reisner
2011-08-30 9:05 ` [PATCH 08/15] drbd: use clear_bit_unlock() where appropriate Philipp Reisner
2011-08-30 9:05 ` [PATCH 09/15] lru_cache.h: fix comments referring to ts_ instead of lc_ Philipp Reisner
2011-08-30 9:05 ` [PATCH 10/15] lru_cache: consolidate lc_get and lc_try_get Philipp Reisner
2011-08-30 9:05 ` [PATCH 11/15] drbd: allow to select specific bitmap pages for writeout Philipp Reisner
2011-08-30 9:05 ` [PATCH 12/15] lru_cache: allow multiple changes per transaction Philipp Reisner
2011-08-30 9:05 ` [PATCH 13/15] drbd: new on-disk activity log transaction format Philipp Reisner
2011-08-30 9:05 ` [PATCH 14/15] drbd: silence some log messages on bitmap IO Philipp Reisner
2011-08-30 9:05 ` [PATCH 15/15] drbd: fix a wrong likely(), updated comments Philipp Reisner
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1314695149-387-3-git-send-email-philipp.reisner@linbit.com \
--to=philipp.reisner@linbit.com \
--cc=axboe@kernel.dk \
--cc=drbd-dev@lists.linbit.com \
--cc=linux-kernel@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®