[thirdparty/util-linux.git] / libfdisk / src / table.c


#include "fdiskP.h"

/**
 * fdisk_new_table:
 *
 * The table is a container for struct fdisk_partition entries. The container
 * does not have any real connection with label (partition table) and with
 * real on-disk data.
 *
 * Returns: newly allocated table struct.
 */
struct fdisk_table *fdisk_new_table(void)
{
	struct fdisk_table *tb = NULL;

	tb = calloc(1, sizeof(*tb));
	if (!tb)
		return NULL;

	DBG(TAB, ul_debugobj(tb, "alloc"));
	tb->refcount = 1;
	INIT_LIST_HEAD(&tb->parts);
	return tb;
}

/**
 * fdisk_reset_table:
 * @tb: tab pointer
 *
 * Removes all entries (partitions) from the table. The parititons with zero
 * reference count will be deallocated. This function does not modify partition
 * table.
 *
 * Returns: 0 on success or negative number in case of error.
 */
int fdisk_reset_table(struct fdisk_table *tb)
{
	if (!tb)
		return -EINVAL;

	DBG(TAB, ul_debugobj(tb, "reset"));

	while (!list_empty(&tb->parts)) {
		struct fdisk_partition *pa = list_entry(tb->parts.next,
				                  struct fdisk_partition, parts);
		fdisk_table_remove_partition(tb, pa);
	}

	tb->nents = 0;
	return 0;
}

/**
 * fdisk_ref_table:
 * @tb: table pointer
 *
 * Incremparts reference counter.
 */
void fdisk_ref_table(struct fdisk_table *tb)
{
	if (tb)
		tb->refcount++;
}

/**
 * fdisk_unref_table:
 * @tb: table pointer
 *
 * De-incremparts reference counter, on zero the @tb is automatically
 * deallocated.
 */
void fdisk_unref_table(struct fdisk_table *tb)
{
	if (!tb)
		return;

	tb->refcount--;
	if (tb->refcount <= 0) {
		fdisk_reset_table(tb);

		DBG(TAB, ul_debugobj(tb, "free"));
		free(tb);
	}
}

/**
 * fdisk_table_is_empty:
 * @tb: pointer to tab
 *
 * Returns: 1 if the table is without filesystems, or 0.
 */
int fdisk_table_is_empty(struct fdisk_table *tb)
{
	return tb == NULL || list_empty(&tb->parts) ? 1 : 0;
}

/**
 * fdisk_table_get_nents:
 * @tb: pointer to tab
 *
 * Returns: number of entries in table.
 */
size_t fdisk_table_get_nents(struct fdisk_table *tb)
{
	return tb ? tb->nents : 0;
}

/**
 * fdisk_table_next_partition:
 * @tb: tab pointer
 * @itr: iterator
 * @pa: returns the next tab entry
 *
 * Returns: 0 on success, negative number in case of error or 1 at the end of list.
 *
 * Example:
 * <informalexample>
 *   <programlisting>
 *	while(fdisk_table_next_partition(tb, itr, &pa) == 0) {
 *		...
 *	}
 *   </programlisting>
 * </informalexample>
 */
int fdisk_table_next_partition(
			struct fdisk_table *tb,
			struct fdisk_iter *itr,
			struct fdisk_partition **pa)
{
	int rc = 1;

	assert(tb);
	assert(itr);
	assert(pa);

	if (!tb || !itr || !pa)
		return -EINVAL;
	*pa = NULL;

	if (!itr->head)
		FDISK_ITER_INIT(itr, &tb->parts);
	if (itr->p != itr->head) {
		FDISK_ITER_ITERATE(itr, *pa, struct fdisk_partition, parts);
		rc = 0;
	}

	return rc;
}

struct fdisk_partition *fdisk_table_get_partition(
			struct fdisk_table *tb,
			size_t n)
{
	struct fdisk_partition *pa = NULL;
	struct fdisk_iter itr;

	if (!tb)
		return NULL;

	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);

	while (fdisk_table_next_partition(tb, &itr, &pa) == 0) {
		if (n == 0)
			return pa;
		n--;
	}

	return NULL;
}

/**
 * fdisk_table_add_partition
 * @tb: tab pointer
 * @pa: new entry
 *
 * Adds a new entry to table and increment @pa reference counter. Don't forget to
 * use fdisk_unref_pa() after fdisk_table_add_partition() if you want to keep
 * the @pa referenced by the table only.
 *
 * Returns: 0 on success or negative number in case of error.
 */
int fdisk_table_add_partition(struct fdisk_table *tb, struct fdisk_partition *pa)
{
	assert(tb);
	assert(pa);

	if (!tb || !pa)
		return -EINVAL;

	fdisk_ref_partition(pa);
	list_add_tail(&pa->parts, &tb->parts);
	tb->nents++;

	DBG(TAB, ul_debugobj(tb, "add entry %p [start=%ju, end=%ju, size=%ju, %s %s %s]",
			pa, pa->start, pa->end, pa->size,
			fdisk_partition_is_freespace(pa) ? "freespace" : "",
			fdisk_partition_is_nested(pa)    ? "nested"    : "",
			fdisk_partition_is_container(pa) ? "container" : "primary"));
	return 0;
}

/* inserts @pa after @poz */
static int table_insert_partition(
			struct fdisk_table *tb,
			struct fdisk_partition *poz,
			struct fdisk_partition *pa)
{
	assert(tb);
	assert(pa);

	fdisk_ref_partition(pa);
	if (poz)
		list_add(&pa->parts, &poz->parts);
	else
		list_add(&pa->parts, &tb->parts);
	tb->nents++;

	DBG(TAB, ul_debugobj(tb, "insert entry %p pre=%p [start=%ju, end=%ju, size=%ju, %s %s %s]",
			pa, poz ? poz : NULL, pa->start, pa->end, pa->size,
			fdisk_partition_is_freespace(pa) ? "freespace" : "",
			fdisk_partition_is_nested(pa)    ? "nested"    : "",
			fdisk_partition_is_container(pa) ? "container" : "primary"));
	return 0;
}

/**
 * fdisk_table_remove_partition
 * @tb: tab pointer
 * @pa: new entry
 *
 * Removes the @pa from the table and de-increment reference counter of the @pa. The
 * partition with zero reference counter will be deallocated. Don't forget to use
 * fdisk_ref_partition() before call fdisk_table_remove_partition() if you want
 * to use @pa later.
 *
 * Returns: 0 on success or negative number in case of error.
 */
int fdisk_table_remove_partition(struct fdisk_table *tb, struct fdisk_partition *pa)
{
	assert(tb);
	assert(pa);

	if (!tb || !pa)
		return -EINVAL;

	DBG(TAB, ul_debugobj(tb, "remove entry %p", pa));
	list_del(&pa->parts);
	INIT_LIST_HEAD(&pa->parts);

	fdisk_unref_partition(pa);
	tb->nents--;

	return 0;
}

/**
 * fdisk_get_partitions
 * @cxt: fdisk context
 * @tb: returns table
 *
 * This function adds partitions from disklabel to @table, it allocates a new
 * table if if @table points to NULL.
 *
 * Returns 0 on success, otherwise, a corresponding error.
 */
int fdisk_get_partitions(struct fdisk_context *cxt, struct fdisk_table **tb)
{
	size_t i;

	if (!cxt || !cxt->label || !tb)
		return -EINVAL;
	if (!cxt->label->op->get_part)
		return -ENOSYS;

	DBG(CXT, ul_debugobj(cxt, "get table"));

	if (!*tb && !(*tb = fdisk_new_table()))
		return -ENOMEM;

	for (i = 0; i < cxt->label->nparts_max; i++) {
		struct fdisk_partition *pa = NULL;

		if (fdisk_get_partition(cxt, i, &pa) != 0)
			continue;
		if (fdisk_partition_is_used(pa))
			fdisk_table_add_partition(*tb, pa);
		fdisk_unref_partition(pa);
	}

	return 0;
}

typedef	int (*fdisk_partcmp_t)(struct fdisk_partition *, struct fdisk_partition *);

static int cmp_parts_wrapper(struct list_head *a, struct list_head *b, void *data)
{
	struct fdisk_partition *pa = list_entry(a, struct fdisk_partition, parts),
			       *pb = list_entry(b, struct fdisk_partition, parts);

	fdisk_partcmp_t cmp = (fdisk_partcmp_t) data;

	return cmp(pa, pb);
}

/**
 * fdisk_table_sort_partitions:
 * @tb: table
 * @cmp: compare function
 *
 * Sort partition in the table.
 */
int fdisk_table_sort_partitions(struct fdisk_table *tb,
			int (*cmp)(struct fdisk_partition *,
				   struct fdisk_partition *))
{
	if (!tb)
		return -EINVAL;

	list_sort(&tb->parts, cmp_parts_wrapper, (void *) cmp);
	return 0;
}

/* allocates a new freespace description */
static int new_freespace(struct fdisk_context *cxt,
			 uint64_t start,
			 uint64_t end,
			 struct fdisk_partition *parent,
			 struct fdisk_partition **pa)
{
	assert(cxt);
	assert(pa);

	*pa = NULL;

	if (start == end)
		return 0;
	*pa = fdisk_new_partition();
	if (!*pa)
		return -ENOMEM;

	(*pa)->freespace = 1;
	(*pa)->start = fdisk_align_lba_in_range(cxt, start, start, end);
	(*pa)->end = end;
	(*pa)->size = (*pa)->end - (*pa)->start + 1ULL;

	if (parent)
		(*pa)->parent_partno = parent->partno;
	return 0;
}

/* add freespace description to the right place within @tb */
static int table_add_freespace(
			struct fdisk_context *cxt,
			struct fdisk_table *tb,
			uint64_t start,
			uint64_t end,
			struct fdisk_partition *parent)
{
	struct fdisk_partition *pa, *x, *real_parent = NULL, *best = NULL;
	struct fdisk_iter itr;
	int rc = 0;

	assert(tb);

	rc = new_freespace(cxt, start, end, parent, &pa);
	if (rc)
		return -ENOMEM;
	if (!pa)
		return 0;
	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
	if (parent) {
		while (fdisk_table_next_partition(tb, &itr, &x) == 0) {
			if (x->partno == parent->partno) {
				real_parent = x;
				break;
			}
		}
		if (!real_parent) {
			DBG(TAB, ul_debugobj(tb, "not found freespace parent (partno=%zu)",
					parent->partno));
			fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
		}
	}

	while (fdisk_table_next_partition(tb, &itr, &x) == 0) {
		if (x->end < pa->start && (!best || best->end < x->end))
			best = x;
	}

	if (!best && real_parent)
		best = real_parent;
	rc = table_insert_partition(tb, best, pa);

	fdisk_unref_partition(pa);
	return rc;
}

/* analyze @cont(ainer) in @parts and add all detected freespace into @tb, note
 * that @parts has to be sorted by partition starts */
static int check_container_freespace(struct fdisk_context *cxt,
				     struct fdisk_table *parts,
				     struct fdisk_table *tb,
				     struct fdisk_partition *cont)
{
	struct fdisk_iter itr;
	struct fdisk_partition *pa;
	uint64_t x, last, grain;
	uint64_t lastplusoff;
	int rc = 0;

	assert(cxt);
	assert(parts);
	assert(tb);
	assert(cont);
	assert(fdisk_partition_has_start(cont));

	last = fdisk_partition_get_start(cont);
	grain = cxt->grain > cxt->sector_size ?	cxt->grain / cxt->sector_size : 1;
	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);

	while (fdisk_table_next_partition(parts, &itr, &pa) == 0) {
		if (!pa->used || !fdisk_partition_is_nested(pa)
			      || !fdisk_partition_has_start(pa))
			continue;

		lastplusoff = last + cxt->first_lba;
		if (pa->start > lastplusoff && pa->start - lastplusoff > grain)
			rc = table_add_freespace(cxt, tb, lastplusoff, pa->start, cont);
		if (rc)
			return rc;
		last = pa->end;
	}

	/* free-space remaining in extended partition */
	x = fdisk_partition_get_start(cont) + fdisk_partition_get_size(cont) - 1;
	lastplusoff = last + cxt->first_lba;
	if (lastplusoff < x && x - lastplusoff > grain)
		rc = table_add_freespace(cxt, tb, lastplusoff, x, cont);
	return rc;
}


/**
 * fdisk_get_freespaces
 * @cxt: fdisk context
 * @tb: returns table
 *
 * This function adds freespace (described by fdisk_partition) to @table, it
 * allocates a new table if the @table points to NULL.
 *
 * Note that free space smaller than grain (see fdisk_get_grain()) is ignored.

 * Returns 0 on success, otherwise, a corresponding error.
 */
int fdisk_get_freespaces(struct fdisk_context *cxt, struct fdisk_table **tb)
{
	int rc = 0;
	uint64_t last, grain;
	struct fdisk_table *parts = NULL;
	struct fdisk_partition *pa;
	struct fdisk_iter itr;

	DBG(CXT, ul_debugobj(cxt, "get freespace"));

	if (!cxt || !cxt->label || !tb)
		return -EINVAL;
	if (!*tb && !(*tb = fdisk_new_table()))
		return -ENOMEM;

	rc = fdisk_get_partitions(cxt, &parts);
	if (rc)
		goto done;
	fdisk_table_sort_partitions(parts, fdisk_partition_cmp_start);
	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
	last = cxt->first_lba;
	grain = cxt->grain > cxt->sector_size ?	cxt->grain / cxt->sector_size : 1;

	/* analyze gaps between partitions */
	while (rc == 0 && fdisk_table_next_partition(parts, &itr, &pa) == 0) {
		if (!pa->used || pa->wholedisk || fdisk_partition_is_nested(pa)
			      || !fdisk_partition_has_start(pa))
			continue;
		DBG(CXT, ul_debugobj(cxt, "freespace analyze: partno=%zu, start=%ju, end=%ju",
					pa->partno, pa->start, pa->end));
		if (last + grain <= pa->start) {
			rc = table_add_freespace(cxt, *tb,
				last + (last > cxt->first_lba ? 1 : 0),
				pa->start - 1, NULL);
		}
		/* add gaps between logical partitions */
		if (fdisk_partition_is_container(pa))
			rc = check_container_freespace(cxt, parts, *tb, pa);
		last = pa->end;
	}

	/* add free-space behind last partition to the end of the table (so
	 * don't use table_add_freespace()) */
	if (rc == 0 && last + grain < cxt->total_sectors - 1) {
		rc = new_freespace(cxt,
			last + (last > cxt->first_lba ? 1 : 0),
			cxt->last_lba, NULL, &pa);
		if (pa) {
			fdisk_table_add_partition(*tb, pa);
			fdisk_unref_partition(pa);
		}
	}

done:
	fdisk_unref_table(parts);
	return rc;
}

/**
 * fdisk_table_wrong_order:
 * @tb: table
 *
 * Returns: 1 of the table is not in disk order
 */
int fdisk_table_wrong_order(struct fdisk_table *tb)
{
	struct fdisk_partition *pa;
	struct fdisk_iter itr;
	sector_t last = 0;

	DBG(TAB, ul_debugobj(tb, "wrong older check"));

	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
	while (tb && fdisk_table_next_partition(tb, &itr, &pa) == 0) {
		if (!fdisk_partition_has_start(pa))
			continue;
		if (pa->start < last)
			return 1;
		last = pa->start;
	}
	return 0;
}

/**
 * fdisk_apply_table:
 * @cxt: context
 * @tb: table
 *
 * Add partitions from table @tb to the in-memory disk label. See
 * fdisk_add_partition(), fdisk_delete_all_partitions(). The partitons
 * that does not define start (or does not follow the default start)
 * are ingored.
 *
 * Returns: 0 on success, <0 on error.
 */
int fdisk_apply_table(struct fdisk_context *cxt, struct fdisk_table *tb)
{
	struct fdisk_partition *pa;
	struct fdisk_iter itr;
	int rc = 0;

	assert(cxt);
	assert(tb);

	DBG(TAB, ul_debugobj(tb, "applying to context %p", cxt));

	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
	while (tb && fdisk_table_next_partition(tb, &itr, &pa) == 0) {
		if (!fdisk_partition_has_start(pa) && !pa->start_follow_default)
			continue;
		rc = fdisk_add_partition(cxt, pa, NULL);
		if (rc)
			break;
	}

	return rc;
}
Commit	Line	Data
b48cdebc KZ	1
	2	#include "fdiskP.h"
	3
	4	/**
	5	* fdisk_new_table:
	6	*
	7	* The table is a container for struct fdisk_partition entries. The container
	8	* does not have any real connection with label (partition table) and with
	9	* real on-disk data.
	10	*
	11	* Returns: newly allocated table struct.
	12	*/
	13	struct fdisk_table *fdisk_new_table(void)
	14	{
	15	struct fdisk_table *tb = NULL;
	16
	17	tb = calloc(1, sizeof(*tb));
	18	if (!tb)
	19	return NULL;
	20
d71bd2f0	21	DBG(TAB, ul_debugobj(tb, "alloc"));
b48cdebc KZ	22	tb->refcount = 1;
	23	INIT_LIST_HEAD(&tb->parts);
	24	return tb;
	25	}
	26
	27	/**
	28	* fdisk_reset_table:
	29	* @tb: tab pointer
	30	*
3c0e6b15 KZ	31	* Removes all entries (partitions) from the table. The parititons with zero
	32	* reference count will be deallocated. This function does not modify partition
	33	* table.
b48cdebc KZ	34	*
	35	* Returns: 0 on success or negative number in case of error.
	36	*/
	37	int fdisk_reset_table(struct fdisk_table *tb)
	38	{
	39	if (!tb)
	40	return -EINVAL;
	41
d71bd2f0	42	DBG(TAB, ul_debugobj(tb, "reset"));
b48cdebc KZ	43
	44	while (!list_empty(&tb->parts)) {
	45	struct fdisk_partition *pa = list_entry(tb->parts.next,
	46	struct fdisk_partition, parts);
	47	fdisk_table_remove_partition(tb, pa);
	48	}
	49
04406c0d	50	tb->nents = 0;
b48cdebc KZ	51	return 0;
	52	}
	53
	54	/**
	55	* fdisk_ref_table:
	56	* @tb: table pointer
	57	*
	58	* Incremparts reference counter.
	59	*/
	60	void fdisk_ref_table(struct fdisk_table *tb)
	61	{
	62	if (tb)
	63	tb->refcount++;
	64	}
	65
	66	/**
	67	* fdisk_unref_table:
	68	* @tb: table pointer
	69	*
	70	* De-incremparts reference counter, on zero the @tb is automatically
5175ae87	71	* deallocated.
b48cdebc KZ	72	*/
	73	void fdisk_unref_table(struct fdisk_table *tb)
	74	{
	75	if (!tb)
	76	return;
	77
	78	tb->refcount--;
	79	if (tb->refcount <= 0) {
	80	fdisk_reset_table(tb);
	81
d71bd2f0	82	DBG(TAB, ul_debugobj(tb, "free"));
b48cdebc KZ	83	free(tb);
	84	}
	85	}
	86
	87	/**
	88	* fdisk_table_is_empty:
	89	* @tb: pointer to tab
	90	*
	91	* Returns: 1 if the table is without filesystems, or 0.
	92	*/
	93	int fdisk_table_is_empty(struct fdisk_table *tb)
	94	{
b48cdebc KZ	95	return tb == NULL \|\| list_empty(&tb->parts) ? 1 : 0;
	96	}
	97
04406c0d KZ	98	/**
	99	* fdisk_table_get_nents:
	100	* @tb: pointer to tab
	101	*
	102	* Returns: number of entries in table.
	103	*/
e54b1c6f	104	size_t fdisk_table_get_nents(struct fdisk_table *tb)
04406c0d KZ	105	{
	106	return tb ? tb->nents : 0;
	107	}
6c89f750 KZ	108
	109	/**
	110	* fdisk_table_next_partition:
	111	* @tb: tab pointer
	112	* @itr: iterator
	113	* @pa: returns the next tab entry
	114	*
	115	* Returns: 0 on success, negative number in case of error or 1 at the end of list.
	116	*
	117	* Example:
	118	* <informalexample>
	119	* <programlisting>
	120	* while(fdisk_table_next_partition(tb, itr, &pa) == 0) {
	121	* ...
	122	* }
	123	* </programlisting>
	124	* </informalexample>
	125	*/
	126	int fdisk_table_next_partition(
	127	struct fdisk_table *tb,
	128	struct fdisk_iter *itr,
	129	struct fdisk_partition **pa)
	130	{
	131	int rc = 1;
	132
	133	assert(tb);
	134	assert(itr);
	135	assert(pa);
	136
	137	if (!tb \|\| !itr \|\| !pa)
	138	return -EINVAL;
	139	*pa = NULL;
	140
	141	if (!itr->head)
	142	FDISK_ITER_INIT(itr, &tb->parts);
	143	if (itr->p != itr->head) {
	144	FDISK_ITER_ITERATE(itr, *pa, struct fdisk_partition, parts);
	145	rc = 0;
	146	}
	147
	148	return rc;
	149	}
	150
28b6a23c KZ	151	struct fdisk_partition *fdisk_table_get_partition(
	152	struct fdisk_table *tb,
	153	size_t n)
	154	{
	155	struct fdisk_partition *pa = NULL;
	156	struct fdisk_iter itr;
	157
	158	if (!tb)
	159	return NULL;
	160
	161	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
	162
	163	while (fdisk_table_next_partition(tb, &itr, &pa) == 0) {
	164	if (n == 0)
	165	return pa;
	166	n--;
	167	}
	168
	169	return NULL;
	170	}
	171
b48cdebc KZ	172	/**
	173	* fdisk_table_add_partition
	174	* @tb: tab pointer
	175	* @pa: new entry
	176	*
	177	* Adds a new entry to table and increment @pa reference counter. Don't forget to
	178	* use fdisk_unref_pa() after fdisk_table_add_partition() if you want to keep
	179	* the @pa referenced by the table only.
	180	*
	181	* Returns: 0 on success or negative number in case of error.
	182	*/
	183	int fdisk_table_add_partition(struct fdisk_table tb, struct fdisk_partition pa)
	184	{
	185	assert(tb);
	186	assert(pa);
	187
	188	if (!tb \|\| !pa)
	189	return -EINVAL;
	190
	191	fdisk_ref_partition(pa);
	192	list_add_tail(&pa->parts, &tb->parts);
04406c0d	193	tb->nents++;
b48cdebc	194
d71bd2f0	195	DBG(TAB, ul_debugobj(tb, "add entry %p [start=%ju, end=%ju, size=%ju, %s %s %s]",
e77313a6 KZ	196	pa, pa->start, pa->end, pa->size,
	197	fdisk_partition_is_freespace(pa) ? "freespace" : "",
	198	fdisk_partition_is_nested(pa) ? "nested" : "",
5139eca7	199	fdisk_partition_is_container(pa) ? "container" : "primary"));
b48cdebc KZ	200	return 0;
	201	}
	202
2cec7949 KZ	203	/* inserts @pa after @poz */
	204	static int table_insert_partition(
	205	struct fdisk_table *tb,
	206	struct fdisk_partition *poz,
	207	struct fdisk_partition *pa)
	208	{
	209	assert(tb);
	210	assert(pa);
	211
	212	fdisk_ref_partition(pa);
	213	if (poz)
	214	list_add(&pa->parts, &poz->parts);
	215	else
	216	list_add(&pa->parts, &tb->parts);
	217	tb->nents++;
	218
d71bd2f0	219	DBG(TAB, ul_debugobj(tb, "insert entry %p pre=%p [start=%ju, end=%ju, size=%ju, %s %s %s]",
5139eca7 KZ	220	pa, poz ? poz : NULL, pa->start, pa->end, pa->size,
	221	fdisk_partition_is_freespace(pa) ? "freespace" : "",
	222	fdisk_partition_is_nested(pa) ? "nested" : "",
	223	fdisk_partition_is_container(pa) ? "container" : "primary"));
2cec7949 KZ	224	return 0;
	225	}
	226
b48cdebc KZ	227	/**
	228	* fdisk_table_remove_partition
	229	* @tb: tab pointer
	230	* @pa: new entry
	231	*
	232	* Removes the @pa from the table and de-increment reference counter of the @pa. The
	233	* partition with zero reference counter will be deallocated. Don't forget to use
	234	* fdisk_ref_partition() before call fdisk_table_remove_partition() if you want
	235	* to use @pa later.
	236	*
	237	* Returns: 0 on success or negative number in case of error.
	238	*/
	239	int fdisk_table_remove_partition(struct fdisk_table tb, struct fdisk_partition pa)
	240	{
	241	assert(tb);
	242	assert(pa);
	243
	244	if (!tb \|\| !pa)
	245	return -EINVAL;
	246
d71bd2f0	247	DBG(TAB, ul_debugobj(tb, "remove entry %p", pa));
b48cdebc KZ	248	list_del(&pa->parts);
	249	INIT_LIST_HEAD(&pa->parts);
	250
	251	fdisk_unref_partition(pa);
04406c0d KZ	252	tb->nents--;
04406c0d KZ	253
b48cdebc KZ	254	return 0;
b48cdebc KZ	255	}
6c89f750	256
2cec7949 KZ	257	/**
	258	* fdisk_get_partitions
	259	* @cxt: fdisk context
	260	* @tb: returns table
	261	*
	262	* This function adds partitions from disklabel to @table, it allocates a new
	263	* table if if @table points to NULL.
	264	*
	265	* Returns 0 on success, otherwise, a corresponding error.
	266	*/
	267	int fdisk_get_partitions(struct fdisk_context cxt, struct fdisk_table *tb)
	268	{
	269	size_t i;
	270
	271	if (!cxt \|\| !cxt->label \|\| !tb)
	272	return -EINVAL;
	273	if (!cxt->label->op->get_part)
	274	return -ENOSYS;
	275
d71bd2f0	276	DBG(CXT, ul_debugobj(cxt, "get table"));
2cec7949 KZ	277
	278	if (!tb && !(tb = fdisk_new_table()))
	279	return -ENOMEM;
	280
	281	for (i = 0; i < cxt->label->nparts_max; i++) {
	282	struct fdisk_partition *pa = NULL;
	283
	284	if (fdisk_get_partition(cxt, i, &pa) != 0)
	285	continue;
	286	if (fdisk_partition_is_used(pa))
	287	fdisk_table_add_partition(*tb, pa);
	288	fdisk_unref_partition(pa);
	289	}
	290
	291	return 0;
	292	}
	293
e5c93999 KZ	294	typedef int (fdisk_partcmp_t)(struct fdisk_partition , struct fdisk_partition *);
	295
	296	static int cmp_parts_wrapper(struct list_head a, struct list_head b, void *data)
	297	{
	298	struct fdisk_partition *pa = list_entry(a, struct fdisk_partition, parts),
	299	*pb = list_entry(b, struct fdisk_partition, parts);
	300
	301	fdisk_partcmp_t cmp = (fdisk_partcmp_t) data;
	302
	303	return cmp(pa, pb);
	304	}
	305
5175ae87 KZ	306	/**
	307	* fdisk_table_sort_partitions:
	308	* @tb: table
	309	* @cmp: compare function
	310	*
	311	* Sort partition in the table.
	312	*/
e5c93999 KZ	313	int fdisk_table_sort_partitions(struct fdisk_table *tb,
	314	int (cmp)(struct fdisk_partition ,
	315	struct fdisk_partition *))
	316	{
	317	if (!tb)
	318	return -EINVAL;
	319
	320	list_sort(&tb->parts, cmp_parts_wrapper, (void *) cmp);
	321	return 0;
	322	}
	323
5139eca7 KZ	324	/* allocates a new freespace description */
	325	static int new_freespace(struct fdisk_context *cxt,
	326	uint64_t start,
	327	uint64_t end,
	328	struct fdisk_partition *parent,
	329	struct fdisk_partition **pa)
	330	{
	331	assert(cxt);
	332	assert(pa);
	333
	334	*pa = NULL;
	335
	336	if (start == end)
	337	return 0;
	338	*pa = fdisk_new_partition();
	339	if (!*pa)
	340	return -ENOMEM;
	341
	342	(*pa)->freespace = 1;
	343	(*pa)->start = fdisk_align_lba_in_range(cxt, start, start, end);
	344	(*pa)->end = end;
	345	(pa)->size = (pa)->end - (*pa)->start + 1ULL;
	346
	347	if (parent)
	348	(*pa)->parent_partno = parent->partno;
	349	return 0;
	350	}
	351
	352	/* add freespace description to the right place within @tb */
03643931	353	static int table_add_freespace(
81c29a73	354	struct fdisk_context *cxt,
6c89f750 KZ	355	struct fdisk_table *tb,
6c89f750 KZ	356	uint64_t start,
2cec7949	357	uint64_t end,
bd5e8291	358	struct fdisk_partition *parent)
6c89f750	359	{
bd5e8291 KZ	360	struct fdisk_partition pa, x, real_parent = NULL, best = NULL;
bd5e8291 KZ	361	struct fdisk_iter itr;
5139eca7	362	int rc = 0;
6c89f750 KZ	363
	364	assert(tb);
	365
5139eca7 KZ	366	rc = new_freespace(cxt, start, end, parent, &pa);
5139eca7 KZ	367	if (rc)
2cec7949	368	return -ENOMEM;
5139eca7 KZ	369	if (!pa)
5139eca7 KZ	370	return 0;
bd5e8291	371	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
bd5e8291	372	if (parent) {
2cec7949	373	while (fdisk_table_next_partition(tb, &itr, &x) == 0) {
bd5e8291 KZ	374	if (x->partno == parent->partno) {
	375	real_parent = x;
	376	break;
	377	}
	378	}
	379	if (!real_parent) {
73548d6e	380	DBG(TAB, ul_debugobj(tb, "not found freespace parent (partno=%zu)",
bd5e8291 KZ	381	parent->partno));
bd5e8291 KZ	382	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
2cec7949	383	}
2cec7949	384	}
bd5e8291 KZ	385
	386	while (fdisk_table_next_partition(tb, &itr, &x) == 0) {
	387	if (x->end < pa->start && (!best \|\| best->end < x->end))
	388	best = x;
	389	}
	390
	391	if (!best && real_parent)
	392	best = real_parent;
	393	rc = table_insert_partition(tb, best, pa);
	394
6c89f750 KZ	395	fdisk_unref_partition(pa);
	396	return rc;
	397	}
2cec7949	398
5139eca7 KZ	399	/* analyze @cont(ainer) in @parts and add all detected freespace into @tb, note
	400	* that @parts has to be sorted by partition starts */
	401	static int check_container_freespace(struct fdisk_context *cxt,
	402	struct fdisk_table *parts,
	403	struct fdisk_table *tb,
	404	struct fdisk_partition *cont)
	405	{
	406	struct fdisk_iter itr;
	407	struct fdisk_partition *pa;
	408	uint64_t x, last, grain;
5fd7160e	409	uint64_t lastplusoff;
5139eca7 KZ	410	int rc = 0;
	411
	412	assert(cxt);
	413	assert(parts);
	414	assert(tb);
	415	assert(cont);
ecf40cda	416	assert(fdisk_partition_has_start(cont));
5139eca7	417
5fd7160e	418	last = fdisk_partition_get_start(cont);
5139eca7 KZ	419	grain = cxt->grain > cxt->sector_size ? cxt->grain / cxt->sector_size : 1;
	420	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
	421
	422	while (fdisk_table_next_partition(parts, &itr, &pa) == 0) {
ecf40cda KZ	423	if (!pa->used \|\| !fdisk_partition_is_nested(pa)
ecf40cda KZ	424	\|\| !fdisk_partition_has_start(pa))
5139eca7	425	continue;
5fd7160e KZ	426
	427	lastplusoff = last + cxt->first_lba;
	428	if (pa->start > lastplusoff && pa->start - lastplusoff > grain)
	429	rc = table_add_freespace(cxt, tb, lastplusoff, pa->start, cont);
5139eca7 KZ	430	if (rc)
	431	return rc;
	432	last = pa->end;
	433	}
	434
	435	/* free-space remaining in extended partition */
	436	x = fdisk_partition_get_start(cont) + fdisk_partition_get_size(cont) - 1;
5fd7160e KZ	437	lastplusoff = last + cxt->first_lba;
	438	if (lastplusoff < x && x - lastplusoff > grain)
	439	rc = table_add_freespace(cxt, tb, lastplusoff, x, cont);
5139eca7 KZ	440	return rc;
	441	}
	442
2cec7949	443
6c89f750	444	/**
2cec7949	445	* fdisk_get_freespaces
6c89f750	446	* @cxt: fdisk context
2cec7949	447	* @tb: returns table
6c89f750	448	*
2cec7949	449	* This function adds freespace (described by fdisk_partition) to @table, it
5139eca7	450	* allocates a new table if the @table points to NULL.
c743bf74	451	*
5175ae87	452	* Note that free space smaller than grain (see fdisk_get_grain()) is ignored.
2cec7949	453
6c89f750 KZ	454	* Returns 0 on success, otherwise, a corresponding error.
6c89f750 KZ	455	*/
2cec7949	456	int fdisk_get_freespaces(struct fdisk_context cxt, struct fdisk_table *tb)
6c89f750	457	{
bd5e8291	458	int rc = 0;
6c89f750	459	uint64_t last, grain;
e5c93999	460	struct fdisk_table *parts = NULL;
5139eca7	461	struct fdisk_partition *pa;
e5c93999	462	struct fdisk_iter itr;
6c89f750	463
d71bd2f0	464	DBG(CXT, ul_debugobj(cxt, "get freespace"));
2cec7949	465
6c89f750 KZ	466	if (!cxt \|\| !cxt->label \|\| !tb)
6c89f750 KZ	467	return -EINVAL;
2cec7949 KZ	468	if (!tb && !(tb = fdisk_new_table()))
2cec7949 KZ	469	return -ENOMEM;
5139eca7	470
e5c93999 KZ	471	rc = fdisk_get_partitions(cxt, &parts);
	472	if (rc)
	473	goto done;
e5c93999 KZ	474	fdisk_table_sort_partitions(parts, fdisk_partition_cmp_start);
e5c93999 KZ	475	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
6c89f750	476	last = cxt->first_lba;
03643931	477	grain = cxt->grain > cxt->sector_size ? cxt->grain / cxt->sector_size : 1;
6c89f750	478
e5c93999	479	/* analyze gaps between partitions */
5139eca7	480	while (rc == 0 && fdisk_table_next_partition(parts, &itr, &pa) == 0) {
ecf40cda KZ	481	if (!pa->used \|\| pa->wholedisk \|\| fdisk_partition_is_nested(pa)
ecf40cda KZ	482	\|\| !fdisk_partition_has_start(pa))
03643931	483	continue;
d71bd2f0	484	DBG(CXT, ul_debugobj(cxt, "freespace analyze: partno=%zu, start=%ju, end=%ju",
e5c93999	485	pa->partno, pa->start, pa->end));
c743bf74	486	if (last + grain <= pa->start) {
03643931	487	rc = table_add_freespace(cxt, *tb,
6c89f750	488	last + (last > cxt->first_lba ? 1 : 0),
bd5e8291	489	pa->start - 1, NULL);
6c89f750	490	}
5139eca7 KZ	491	/* add gaps between logical partitions */
	492	if (fdisk_partition_is_container(pa))
	493	rc = check_container_freespace(cxt, parts, *tb, pa);
6c89f750	494	last = pa->end;
6c89f750 KZ	495	}
6c89f750 KZ	496
5139eca7 KZ	497	/* add free-space behind last partition to the end of the table (so
	498	* don't use table_add_freespace()) */
	499	if (rc == 0 && last + grain < cxt->total_sectors - 1) {
	500	rc = new_freespace(cxt,
6c89f750	501	last + (last > cxt->first_lba ? 1 : 0),
5139eca7 KZ	502	cxt->last_lba, NULL, &pa);
	503	if (pa) {
	504	fdisk_table_add_partition(*tb, pa);
	505	fdisk_unref_partition(pa);
03643931	506	}
aa423fd3	507	}
03643931	508
e5c93999 KZ	509	done:
e5c93999 KZ	510	fdisk_unref_table(parts);
2cec7949	511	return rc;
6c89f750 KZ	512	}
6c89f750 KZ	513
8b60872e KZ	514	/**
	515	* fdisk_table_wrong_order:
	516	* @tb: table
	517	*
	518	* Returns: 1 of the table is not in disk order
	519	*/
	520	int fdisk_table_wrong_order(struct fdisk_table *tb)
	521	{
	522	struct fdisk_partition *pa;
	523	struct fdisk_iter itr;
	524	sector_t last = 0;
	525
	526	DBG(TAB, ul_debugobj(tb, "wrong older check"));
	527
	528	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
	529	while (tb && fdisk_table_next_partition(tb, &itr, &pa) == 0) {
ecf40cda KZ	530	if (!fdisk_partition_has_start(pa))
ecf40cda KZ	531	continue;
8b60872e KZ	532	if (pa->start < last)
	533	return 1;
	534	last = pa->start;
	535	}
	536	return 0;
	537	}
385810d2	538
3c0e6b15 KZ	539	/**
	540	* fdisk_apply_table:
	541	* @cxt: context
	542	* @tb: table
	543	*
	544	* Add partitions from table @tb to the in-memory disk label. See
3186f4a9 KZ	545	* fdisk_add_partition(), fdisk_delete_all_partitions(). The partitons
	546	* that does not define start (or does not follow the default start)
	547	* are ingored.
3c0e6b15 KZ	548	*
	549	* Returns: 0 on success, <0 on error.
	550	*/
	551	int fdisk_apply_table(struct fdisk_context cxt, struct fdisk_table tb)
	552	{
	553	struct fdisk_partition *pa;
	554	struct fdisk_iter itr;
	555	int rc = 0;
	556
	557	assert(cxt);
	558	assert(tb);
	559
	560	DBG(TAB, ul_debugobj(tb, "applying to context %p", cxt));
	561
	562	fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
	563	while (tb && fdisk_table_next_partition(tb, &itr, &pa) == 0) {
ecf40cda	564	if (!fdisk_partition_has_start(pa) && !pa->start_follow_default)
3186f4a9	565	continue;
c3bc7483	566	rc = fdisk_add_partition(cxt, pa, NULL);
3c0e6b15 KZ	567	if (rc)
	568	break;
	569	}
	570
	571	return rc;
	572	}
	573