From aedea1300349e088286d63a4bcd16a85d12c6a7c Mon Sep 17 00:00:00 2001
From: "Richard W.M. Jones" <rjones@redhat.com>
Date: Thu, 1 Jan 1970 00:00:00 +0000
Subject: [PATCH] get_owners (query) function.

---
 lib/diskimage.ml  | 28 +++++++++++++++++++++++++---
 lib/diskimage.mli | 25 +++++++++++++++++++++++++
 2 files changed, 50 insertions(+), 3 deletions(-)

diff --git a/lib/diskimage.ml b/lib/diskimage.ml
index 71f56b4..b12ba0e 100644
--- a/lib/diskimage.ml
+++ b/lib/diskimage.ml
@@ -303,12 +303,15 @@ let print_binary_tree leaf_printer node_printer tree =
   print tree;
   eprintf "}\n";
 
+type owner =
+    [ `Filesystem of filesystem
+    | `Partitions of partitions
+    | `PhysicalVolume of pv ]
+
 (* A segment describes the owner of a range of disk addresses. *)
 type segment =
     int63 * int63 *			(* disk offset, size of segment *)
-      [ `Filesystem of filesystem
-      | `Partitions of partitions
-      | `PhysicalVolume of pv ] *	(* owner *)
+      owner *				(* owner *)
       int63				(* owner offset *)
 
 type interval = int63 * int63		(* start point, end point (bytes) *)
@@ -657,3 +660,22 @@ let create_ownership machine =
 
   (* Return the ownership structure. *)
   ownership
+
+let get_owners machine ownership disk offset =
+  (* Get the correct tree. *)
+  let tree = List.assoc disk ownership in
+
+  let rec query = function
+    | Leaf (_, segments) -> segments
+    | Node ((Leaf ((_, leftend), _) | Node (_, ((_, leftend), _), _) as left),
+	    (_, segments),
+	    right) ->
+	let subsegments =
+	  if offset < leftend then query left else query right in
+	segments @ subsegments
+  in
+  let owners = query tree in
+
+  List.map (
+    fun (_, _, owner, owner_offset) -> (owner, offset -^ owner_offset)
+  ) owners
diff --git a/lib/diskimage.mli b/lib/diskimage.mli
index 2373341..22ba927 100644
--- a/lib/diskimage.mli
+++ b/lib/diskimage.mli
@@ -303,6 +303,31 @@ val create_ownership : machine -> ownership
       ultimate filesystem, etc., which owns each one).
   *)
 
+type owner =
+    [ `Filesystem of filesystem
+    | `Partitions of partitions
+    | `PhysicalVolume of pv ]
+
+val get_owners :
+  machine -> ownership -> device -> Int63.t -> (owner * Int63.t) list
+  (** [get_owners machine ownership disk offset] returns the
+      owners (filesystems, etc.) which reside on block device [disk]
+      at the given byte offset.  [disk] must be a block device
+      of the machine.
+
+      Returns a list of [(owner, owner_offset)] where [owner]
+      is the filesystem, etc., and [owner_offset] is the byte
+      offset relative to the owner.
+
+      It is common for there to be multiple owners: for example
+      in the case where a filesystem is created on a partition,
+      both the filesystem ([`Filesystem fs]) and
+      partition scheme ([`Partitions parts]) will be returned.
+
+      This function is efficient.  {!create_ownership} creates
+      a tree structure which allows ownership to be determined
+      in just a few steps. *)
+
 (** {2 Debugging} *)
 
 val debug : bool ref
-- 
1.8.3.1