2 libparted - a library for manipulating disk partitions
3 Copyright (C) 2000-2001, 2007, 2009-2011 Free Software Foundation, Inc.
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
20 * \addtogroup PedConstraint
22 * \brief Constraint solver interface.
24 * Constraints are used to communicate restrictions on operations Constraints
25 * are restrictions on the location and alignment of the start and end of a
26 * partition, and the minimum and maximum size.
28 * Constraints are closed under intersection (for the proof see the source
29 * code). For background information see the Chinese Remainder Theorem.
31 * This interface consists of construction constraints, finding the intersection
32 * of constraints, and finding solutions to constraints.
34 * The constraint solver allows you to specify constraints on where a partition
35 * or file system (or any PedGeometry) may be placed/resized/etc. For example,
36 * you might want to make sure that a file system is at least 10 Gb, or that it
37 * starts at the beginning of new cylinder.
39 * The constraint solver in this file unifies solver in geom.c (which allows you
40 * to specify constraints on ranges) and natmath.c (which allows you to specify
41 * alignment constraints).
47 #include <parted/parted.h>
48 #include <parted/debug.h>
52 * Initializes a pre-allocated piece of memory to contain a constraint
53 * with the supplied default values.
55 * \return \c 0 on failure.
59 PedConstraint* constraint,
60 const PedAlignment* start_align,
61 const PedAlignment* end_align,
62 const PedGeometry* start_range,
63 const PedGeometry* end_range,
67 PED_ASSERT (constraint != NULL);
68 PED_ASSERT (start_range != NULL);
69 PED_ASSERT (end_range != NULL);
70 PED_ASSERT (min_size > 0);
71 PED_ASSERT (max_size > 0);
73 constraint->start_align = ped_alignment_duplicate (start_align);
74 constraint->end_align = ped_alignment_duplicate (end_align);
75 constraint->start_range = ped_geometry_duplicate (start_range);
76 constraint->end_range = ped_geometry_duplicate (end_range);
77 constraint->min_size = min_size;
78 constraint->max_size = max_size;
84 * Convenience wrapper for ped_constraint_init().
86 * Allocates a new piece of memory and initializes the constraint.
88 * \return \c NULL on failure.
92 const PedAlignment* start_align,
93 const PedAlignment* end_align,
94 const PedGeometry* start_range,
95 const PedGeometry* end_range,
99 PedConstraint* constraint;
101 constraint = (PedConstraint*) ped_malloc (sizeof (PedConstraint));
104 if (!ped_constraint_init (constraint, start_align, end_align,
105 start_range, end_range, min_size, max_size))
106 goto error_free_constraint;
109 error_free_constraint:
116 * Return a constraint that requires a region to be entirely contained inside
117 * \p max, and to entirely contain \p min.
119 * \return \c NULL on failure.
122 ped_constraint_new_from_min_max (
123 const PedGeometry* min,
124 const PedGeometry* max)
126 PedGeometry start_range;
127 PedGeometry end_range;
129 PED_ASSERT (min != NULL);
130 PED_ASSERT (max != NULL);
131 PED_ASSERT (ped_geometry_test_inside (max, min));
133 ped_geometry_init (&start_range, min->dev, max->start,
134 min->start - max->start + 1);
135 ped_geometry_init (&end_range, min->dev, min->end,
136 max->end - min->end + 1);
138 return ped_constraint_new (
139 ped_alignment_any, ped_alignment_any,
140 &start_range, &end_range,
141 min->length, max->length);
145 * Return a constraint that requires a region to entirely contain \p min.
147 * \return \c NULL on failure.
150 ped_constraint_new_from_min (const PedGeometry* min)
152 PedGeometry full_dev;
154 PED_ASSERT (min != NULL);
156 ped_geometry_init (&full_dev, min->dev, 0, min->dev->length);
157 return ped_constraint_new_from_min_max (min, &full_dev);
161 * Return a constraint that requires a region to be entirely contained inside
164 * \return \c NULL on failure.
167 ped_constraint_new_from_max (const PedGeometry* max)
169 PED_ASSERT (max != NULL);
171 return ped_constraint_new (
172 ped_alignment_any, ped_alignment_any,
173 max, max, 1, max->length);
177 * Duplicate a constraint.
179 * \return \c NULL on failure.
182 ped_constraint_duplicate (const PedConstraint* constraint)
184 PED_ASSERT (constraint != NULL);
186 return ped_constraint_new (
187 constraint->start_align,
188 constraint->end_align,
189 constraint->start_range,
190 constraint->end_range,
191 constraint->min_size,
192 constraint->max_size);
196 * Return a constraint that requires a region to satisfy both \p a and \p b.
198 * Moreover, any region satisfying \p a and \p b will also satisfy the returned
201 * \return \c NULL if no solution could be found (note that \c NULL is a valid
205 ped_constraint_intersect (const PedConstraint* a, const PedConstraint* b)
207 PedAlignment* start_align;
208 PedAlignment* end_align;
209 PedGeometry* start_range;
210 PedGeometry* end_range;
213 PedConstraint* constraint;
218 start_align = ped_alignment_intersect (a->start_align, b->start_align);
221 end_align = ped_alignment_intersect (a->end_align, b->end_align);
223 goto empty_destroy_start_align;
224 start_range = ped_geometry_intersect (a->start_range, b->start_range);
226 goto empty_destroy_end_align;
227 end_range = ped_geometry_intersect (a->end_range, b->end_range);
229 goto empty_destroy_start_range;
230 min_size = PED_MAX (a->min_size, b->min_size);
231 max_size = PED_MIN (a->max_size, b->max_size);
233 constraint = ped_constraint_new (
234 start_align, end_align, start_range, end_range,
237 goto empty_destroy_end_range;
239 ped_alignment_destroy (start_align);
240 ped_alignment_destroy (end_align);
241 ped_geometry_destroy (start_range);
242 ped_geometry_destroy (end_range);
245 empty_destroy_end_range:
246 ped_geometry_destroy (end_range);
247 empty_destroy_start_range:
248 ped_geometry_destroy (start_range);
249 empty_destroy_end_align:
250 ped_alignment_destroy (end_align);
251 empty_destroy_start_align:
252 ped_alignment_destroy (start_align);
258 * Release the memory allocated for a PedConstraint constructed with
259 * ped_constraint_init().
262 ped_constraint_done (PedConstraint* constraint)
264 PED_ASSERT (constraint != NULL);
266 ped_alignment_destroy (constraint->start_align);
267 ped_alignment_destroy (constraint->end_align);
268 ped_geometry_destroy (constraint->start_range);
269 ped_geometry_destroy (constraint->end_range);
273 * Release the memory allocated for a PedConstraint constructed with
274 * ped_constraint_new().
277 ped_constraint_destroy (PedConstraint* constraint)
280 ped_constraint_done (constraint);
286 * Return the region within which the start must lie
287 * in order to satisfy a constriant. It takes into account
288 * constraint->start_range, constraint->min_size and constraint->max_size.
289 * All sectors in this range that also satisfy alignment requirements have
290 * an end, such that the (start, end) satisfy the constraint.
293 _constraint_get_canonical_start_range (const PedConstraint* constraint)
295 PedSector first_end_soln;
296 PedSector last_end_soln;
299 PedGeometry start_min_max_range;
301 if (constraint->min_size > constraint->max_size)
304 first_end_soln = ped_alignment_align_down (
305 constraint->end_align, constraint->end_range,
306 constraint->end_range->start);
307 last_end_soln = ped_alignment_align_up (
308 constraint->end_align, constraint->end_range,
309 constraint->end_range->end);
310 if (first_end_soln == -1 || last_end_soln == -1
311 || first_end_soln > last_end_soln
312 || last_end_soln < constraint->min_size)
315 min_start = first_end_soln - constraint->max_size + 1;
318 max_start = last_end_soln - constraint->min_size + 1;
323 &start_min_max_range, constraint->start_range->dev,
324 min_start, max_start - min_start + 1);
326 return ped_geometry_intersect (&start_min_max_range,
327 constraint->start_range);
331 * Return the nearest start that will have at least one other end that
332 * together satisfy the constraint.
335 _constraint_get_nearest_start_soln (const PedConstraint* constraint,
338 PedGeometry* start_range;
341 start_range = _constraint_get_canonical_start_range (constraint);
344 result = ped_alignment_align_nearest (
345 constraint->start_align, start_range, start);
346 ped_geometry_destroy (start_range);
351 * Given a constraint and a start ("half of the solution"), find the
352 * range of all possible ends, such that all (start, end) are solutions
353 * to constraint (subject to additional alignment requirements).
356 _constraint_get_end_range (const PedConstraint* constraint, PedSector start)
358 PedDevice* dev = constraint->end_range->dev;
359 PedSector first_min_max_end;
360 PedSector last_min_max_end;
361 PedGeometry end_min_max_range;
363 if (start + constraint->min_size - 1 > dev->length - 1)
366 first_min_max_end = start + constraint->min_size - 1;
367 last_min_max_end = start + constraint->max_size - 1;
368 if (last_min_max_end > dev->length - 1)
369 last_min_max_end = dev->length - 1;
371 ped_geometry_init (&end_min_max_range, dev,
373 last_min_max_end - first_min_max_end + 1);
375 return ped_geometry_intersect (&end_min_max_range,
376 constraint->end_range);
380 * Given "constraint" and "start", find the end that is nearest to
381 * "end", such that ("start", the end) together form a solution to
385 _constraint_get_nearest_end_soln (const PedConstraint* constraint,
386 PedSector start, PedSector end)
388 PedGeometry* end_range;
391 end_range = _constraint_get_end_range (constraint, start);
395 result = ped_alignment_align_nearest (constraint->end_align, end_range,
397 ped_geometry_destroy (end_range);
402 * Return the nearest region to \p geom that satisfy a \p constraint.
404 * Note that "nearest" is somewhat ambiguous. This function makes
405 * no guarantees about how this ambiguity is resovled.
407 * \return PedGeometry, or NULL when a \p constrain cannot be satisfied
410 ped_constraint_solve_nearest (
411 const PedConstraint* constraint, const PedGeometry* geom)
417 if (constraint == NULL)
420 PED_ASSERT (geom != NULL);
421 PED_ASSERT (constraint->start_range->dev == geom->dev);
423 start = _constraint_get_nearest_start_soln (constraint, geom->start);
426 end = _constraint_get_nearest_end_soln (constraint, start, geom->end);
430 result = ped_geometry_new (geom->dev, start, end - start + 1);
433 PED_ASSERT (ped_constraint_is_solution (constraint, result));
438 * Find the largest region that satisfies a constraint.
440 * There might be more than one solution. This function makes no
441 * guarantees about which solution it will choose in this case.
444 ped_constraint_solve_max (const PedConstraint* constraint)
447 PedGeometry full_dev;
451 dev = constraint->start_range->dev;
452 ped_geometry_init (&full_dev, dev, 0, dev->length - 1);
453 return ped_constraint_solve_nearest (constraint, &full_dev);
457 * Check whether \p geom satisfies the given constraint.
459 * \return \c 1 if it does.
462 ped_constraint_is_solution (const PedConstraint* constraint,
463 const PedGeometry* geom)
465 PED_ASSERT (constraint != NULL);
466 PED_ASSERT (geom != NULL);
468 if (!ped_alignment_is_aligned (constraint->start_align, NULL,
471 if (!ped_alignment_is_aligned (constraint->end_align, NULL, geom->end))
473 if (!ped_geometry_test_sector_inside (constraint->start_range,
476 if (!ped_geometry_test_sector_inside (constraint->end_range, geom->end))
478 if (geom->length < constraint->min_size)
480 if (geom->length > constraint->max_size)
486 * Return a constraint that any region on the given device will satisfy.
489 ped_constraint_any (const PedDevice* dev)
491 PedGeometry full_dev;
493 if (!ped_geometry_init (&full_dev, dev, 0, dev->length))
496 return ped_constraint_new (
506 * Return a constraint that only the given region will satisfy.
509 ped_constraint_exact (const PedGeometry* geom)
511 PedAlignment start_align;
512 PedAlignment end_align;
513 PedGeometry start_sector;
514 PedGeometry end_sector;
517 /* With grain size of 0, it always succeeds. */
518 ok = ped_alignment_init (&start_align, geom->start, 0);
520 ok = ped_alignment_init (&end_align, geom->end, 0);
523 ok = ped_geometry_init (&start_sector, geom->dev, geom->start, 1);
526 ok = ped_geometry_init (&end_sector, geom->dev, geom->end, 1);
530 return ped_constraint_new (&start_align, &end_align,
531 &start_sector, &end_sector, 1,