Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.bin/tmux/layout.c	Lines:	0	324	0.0 %
Date:	2016-12-06	Branches:	0	226	0.0 %


/* $OpenBSD: layout.c,v 1.27 2016/04/29 15:00:48 nicm Exp $ */

/*
 * Copyright (c) 2009 Nicholas Marriott <nicholas.marriott@gmail.com>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF MIND, USE, DATA OR PROFITS, WHETHER
 * IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/types.h>

#include <stdlib.h>

#include "tmux.h"

/*
 * The window layout is a tree of cells each of which can be one of: a
 * left-right container for a list of cells, a top-bottom container for a list
 * of cells, or a container for a window pane.
 *
 * Each window has a pointer to the root of its layout tree (containing its
 * panes), every pane has a pointer back to the cell containing it, and each
 * cell a pointer to its parent cell.
 */

static int	layout_resize_pane_grow(struct layout_cell *, enum layout_type,
		    int);
static int	layout_resize_pane_shrink(struct layout_cell *,
		    enum layout_type, int);
static int	layout_need_status(struct layout_cell *, int);

struct layout_cell *
layout_create_cell(struct layout_cell *lcparent)
{
	struct layout_cell	*lc;

	lc = xmalloc(sizeof *lc);
	lc->type = LAYOUT_WINDOWPANE;
	lc->parent = lcparent;

	TAILQ_INIT(&lc->cells);

	lc->sx = UINT_MAX;
	lc->sy = UINT_MAX;

	lc->xoff = UINT_MAX;
	lc->yoff = UINT_MAX;

	lc->wp = NULL;

	return (lc);
}

void
layout_free_cell(struct layout_cell *lc)
{
	struct layout_cell	*lcchild;

	switch (lc->type) {
	case LAYOUT_LEFTRIGHT:
	case LAYOUT_TOPBOTTOM:
		while (!TAILQ_EMPTY(&lc->cells)) {
			lcchild = TAILQ_FIRST(&lc->cells);
			TAILQ_REMOVE(&lc->cells, lcchild, entry);
			layout_free_cell(lcchild);
		}
		break;
	case LAYOUT_WINDOWPANE:
		if (lc->wp != NULL)
			lc->wp->layout_cell = NULL;
		break;
	}

	free(lc);
}

void
layout_print_cell(struct layout_cell *lc, const char *hdr, u_int n)
{
	struct layout_cell	*lcchild;

	log_debug("%s:%*s%p type %u [parent %p] wp=%p [%u,%u %ux%u]", hdr, n,
	    " ", lc, lc->type, lc->parent, lc->wp, lc->xoff, lc->yoff, lc->sx,
	    lc->sy);
	switch (lc->type) {
	case LAYOUT_LEFTRIGHT:
	case LAYOUT_TOPBOTTOM:
		TAILQ_FOREACH(lcchild, &lc->cells, entry)
		    	layout_print_cell(lcchild, hdr, n + 1);
		break;
	case LAYOUT_WINDOWPANE:
		break;
	}
}

void
layout_set_size(struct layout_cell *lc, u_int sx, u_int sy, u_int xoff,
    u_int yoff)
{
	lc->sx = sx;
	lc->sy = sy;

	lc->xoff = xoff;
	lc->yoff = yoff;
}

void
layout_make_leaf(struct layout_cell *lc, struct window_pane *wp)
{
	lc->type = LAYOUT_WINDOWPANE;

	TAILQ_INIT(&lc->cells);

	wp->layout_cell = lc;
	lc->wp = wp;
}

void
layout_make_node(struct layout_cell *lc, enum layout_type type)
{
	if (type == LAYOUT_WINDOWPANE)
		fatalx("bad layout type");
	lc->type = type;

	TAILQ_INIT(&lc->cells);

	if (lc->wp != NULL)
		lc->wp->layout_cell = NULL;
	lc->wp = NULL;
}

/* Fix cell offsets based on their sizes. */
void
layout_fix_offsets(struct layout_cell *lc)
{
	struct layout_cell	*lcchild;
	u_int			 xoff, yoff;

	if (lc->type == LAYOUT_LEFTRIGHT) {
		xoff = lc->xoff;
		TAILQ_FOREACH(lcchild, &lc->cells, entry) {
			lcchild->xoff = xoff;
			lcchild->yoff = lc->yoff;
			if (lcchild->type != LAYOUT_WINDOWPANE)
				layout_fix_offsets(lcchild);
			xoff += lcchild->sx + 1;
		}
	} else {
		yoff = lc->yoff;
		TAILQ_FOREACH(lcchild, &lc->cells, entry) {
			lcchild->xoff = lc->xoff;
			lcchild->yoff = yoff;
			if (lcchild->type != LAYOUT_WINDOWPANE)
				layout_fix_offsets(lcchild);
			yoff += lcchild->sy + 1;
		}
	}
}

/*
 * Returns 1 if we need to reserve space for the pane status line. This is the
 * case for the most upper panes only.
 */
static int
layout_need_status(struct layout_cell *lc, int at_top)
{
	struct layout_cell	*first_lc;

	if (lc->parent) {
		if (lc->parent->type == LAYOUT_LEFTRIGHT)
			return (layout_need_status(lc->parent, at_top));

		if (at_top)
			first_lc = TAILQ_FIRST(&lc->parent->cells);
		else
			first_lc = TAILQ_LAST(&lc->parent->cells,layout_cells);
		if (lc == first_lc)
			return (layout_need_status(lc->parent, at_top));
		return (0);
	}
	return (1);
}

/* Update pane offsets and sizes based on their cells. */
void
layout_fix_panes(struct window *w, u_int wsx, u_int wsy)
{
	struct window_pane	*wp;
	struct layout_cell	*lc;
	u_int			 sx, sy;
	int			 shift, status, at_top;

	status = options_get_number(w->options, "pane-border-status");
	at_top = (status == 1);
	TAILQ_FOREACH(wp, &w->panes, entry) {
		if ((lc = wp->layout_cell) == NULL)
			continue;

		if (status != 0)
			shift = layout_need_status(lc, at_top);
		else
			shift = 0;

		wp->xoff = lc->xoff;
		wp->yoff = lc->yoff;

		if (shift && at_top)
			wp->yoff += 1;

		/*
		 * Layout cells are limited by the smallest size of other cells
		 * within the same row or column; if this isn't the case
		 * resizing becomes difficult.
		 *
		 * However, panes do not have to take up their entire cell, so
		 * they can be cropped to the window edge if the layout
		 * overflows and they are partly visible.
		 *
		 * This stops cells being hidden unnecessarily.
		 */

		/*
		 * Work out the horizontal size. If the pane is actually
		 * outside the window or the entire pane is already visible,
		 * don't crop.
		 */
		if (lc->xoff >= wsx || lc->xoff + lc->sx < wsx)
			sx = lc->sx;
		else {
			sx = wsx - lc->xoff;
			if (sx < 1)
				sx = lc->sx;
		}

		/*
		 * Similarly for the vertical size; the minimum vertical size
		 * is two because scroll regions cannot be one line.
		 */
		if (lc->yoff >= wsy || lc->yoff + lc->sy < wsy)
			sy = lc->sy;
		else {
			sy = wsy - lc->yoff;
			if (sy < 2)
				sy = lc->sy;
		}

		if (shift)
			sy -= 1;

		window_pane_resize(wp, sx, sy);
	}
}

/* Count the number of available cells in a layout. */
u_int
layout_count_cells(struct layout_cell *lc)
{
	struct layout_cell	*lcchild;
	u_int			 n;

	switch (lc->type) {
	case LAYOUT_WINDOWPANE:
		return (1);
	case LAYOUT_LEFTRIGHT:
	case LAYOUT_TOPBOTTOM:
		n = 0;
		TAILQ_FOREACH(lcchild, &lc->cells, entry)
			n += layout_count_cells(lcchild);
		return (n);
	default:
		fatalx("bad layout type");
	}
}

/* Calculate how much size is available to be removed from a cell. */
u_int
layout_resize_check(struct layout_cell *lc, enum layout_type type)
{
	struct layout_cell	*lcchild;
	u_int			 available, minimum;

	if (lc->type == LAYOUT_WINDOWPANE) {
		/* Space available in this cell only. */
		if (type == LAYOUT_LEFTRIGHT)
			available = lc->sx;
		else
			available = lc->sy;

		if (available > PANE_MINIMUM)
			available -= PANE_MINIMUM;
		else
			available = 0;
	} else if (lc->type == type) {
		/* Same type: total of available space in all child cells. */
		available = 0;
		TAILQ_FOREACH(lcchild, &lc->cells, entry)
			available += layout_resize_check(lcchild, type);
	} else {
		/* Different type: minimum of available space in child cells. */
		minimum = UINT_MAX;
		TAILQ_FOREACH(lcchild, &lc->cells, entry) {
			available = layout_resize_check(lcchild, type);
			if (available < minimum)
				minimum = available;
		}
		available = minimum;
	}

	return (available);
}

/*
 * Adjust cell size evenly, including altering its children. This function
 * expects the change to have already been bounded to the space available.
 */
void
layout_resize_adjust(struct layout_cell *lc, enum layout_type type, int change)
{
	struct layout_cell	*lcchild;

	/* Adjust the cell size. */
	if (type == LAYOUT_LEFTRIGHT)
		lc->sx += change;
	else
		lc->sy += change;

	/* If this is a leaf cell, that is all that is necessary. */
	if (type == LAYOUT_WINDOWPANE)
		return;

	/* Child cell runs in a different direction. */
	if (lc->type != type) {
		TAILQ_FOREACH(lcchild, &lc->cells, entry)
			layout_resize_adjust(lcchild, type, change);
		return;
	}

	/*
	 * Child cell runs in the same direction. Adjust each child equally
	 * until no further change is possible.
	 */
	while (change != 0) {
		TAILQ_FOREACH(lcchild, &lc->cells, entry) {
			if (change == 0)
				break;
			if (change > 0) {
				layout_resize_adjust(lcchild, type, 1);
				change--;
				continue;
			}
			if (layout_resize_check(lcchild, type) > 0) {
				layout_resize_adjust(lcchild, type, -1);
				change++;
			}
		}
	}
}

/* Destroy a cell and redistribute the space. */
void
layout_destroy_cell(struct layout_cell *lc, struct layout_cell **lcroot)
{
	struct layout_cell     *lcother, *lcparent;

	/*
	 * If no parent, this is the last pane so window close is imminent and
	 * there is no need to resize anything.
	 */
	lcparent = lc->parent;
	if (lcparent == NULL) {
		layout_free_cell(lc);
		*lcroot = NULL;
		return;
	}

	/* Merge the space into the previous or next cell. */
	if (lc == TAILQ_FIRST(&lcparent->cells))
		lcother = TAILQ_NEXT(lc, entry);
	else
		lcother = TAILQ_PREV(lc, layout_cells, entry);
	if (lcparent->type == LAYOUT_LEFTRIGHT)
		layout_resize_adjust(lcother, lcparent->type, lc->sx + 1);
	else
		layout_resize_adjust(lcother, lcparent->type, lc->sy + 1);

	/* Remove this from the parent's list. */
	TAILQ_REMOVE(&lcparent->cells, lc, entry);
	layout_free_cell(lc);

	/*
	 * If the parent now has one cell, remove the parent from the tree and
	 * replace it by that cell.
	 */
	lc = TAILQ_FIRST(&lcparent->cells);
	if (TAILQ_NEXT(lc, entry) == NULL) {
		TAILQ_REMOVE(&lcparent->cells, lc, entry);

		lc->parent = lcparent->parent;
		if (lc->parent == NULL) {
			lc->xoff = 0; lc->yoff = 0;
			*lcroot = lc;
		} else
			TAILQ_REPLACE(&lc->parent->cells, lcparent, lc, entry);

		layout_free_cell(lcparent);
	}
}

void
layout_init(struct window *w, struct window_pane *wp)
{
	struct layout_cell	*lc;

	lc = w->layout_root = layout_create_cell(NULL);
	layout_set_size(lc, w->sx, w->sy, 0, 0);
	layout_make_leaf(lc, wp);

	layout_fix_panes(w, w->sx, w->sy);
}

void
layout_free(struct window *w)
{
	layout_free_cell(w->layout_root);
}

/* Resize the entire layout after window resize. */
void
layout_resize(struct window *w, u_int sx, u_int sy)
{
	struct layout_cell	*lc = w->layout_root;
	int			 xlimit, ylimit, xchange, ychange;

	/*
	 * Adjust horizontally. Do not attempt to reduce the layout lower than
	 * the minimum (more than the amount returned by layout_resize_check).
	 *
	 * This can mean that the window size is smaller than the total layout
	 * size: redrawing this is handled at a higher level, but it does leave
	 * a problem with growing the window size here: if the current size is
	 * < the minimum, growing proportionately by adding to each pane is
	 * wrong as it would keep the layout size larger than the window size.
	 * Instead, spread the difference between the minimum and the new size
	 * out proportionately - this should leave the layout fitting the new
	 * window size.
	 */
	xchange = sx - w->sx;
	xlimit = layout_resize_check(lc, LAYOUT_LEFTRIGHT);
	if (xchange < 0 && xchange < -xlimit)
		xchange = -xlimit;
	if (xlimit == 0) {
		if (sx <= lc->sx)	/* lc->sx is minimum possible */
			xchange = 0;
		else
			xchange = sx - lc->sx;
	}
	if (xchange != 0)
		layout_resize_adjust(lc, LAYOUT_LEFTRIGHT, xchange);

	/* Adjust vertically in a similar fashion. */
	ychange = sy - w->sy;
	ylimit = layout_resize_check(lc, LAYOUT_TOPBOTTOM);
	if (ychange < 0 && ychange < -ylimit)
		ychange = -ylimit;
	if (ylimit == 0) {
		if (sy <= lc->sy)	/* lc->sy is minimum possible */
			ychange = 0;
		else
			ychange = sy - lc->sy;
	}
	if (ychange != 0)
		layout_resize_adjust(lc, LAYOUT_TOPBOTTOM, ychange);

	/* Fix cell offsets. */
	layout_fix_offsets(lc);
	layout_fix_panes(w, sx, sy);
}

/* Resize a pane to an absolute size. */
void
layout_resize_pane_to(struct window_pane *wp, enum layout_type type,
    u_int new_size)
{
	struct layout_cell     *lc, *lcparent;
	int			change, size;

	lc = wp->layout_cell;

	/* Find next parent of the same type. */
	lcparent = lc->parent;
	while (lcparent != NULL && lcparent->type != type) {
		lc = lcparent;
		lcparent = lc->parent;
	}
	if (lcparent == NULL)
		return;

	/* Work out the size adjustment. */
	if (type == LAYOUT_LEFTRIGHT)
		size = lc->sx;
	else
		size = lc->sy;
	if (lc == TAILQ_LAST(&lcparent->cells, layout_cells))
		change = size - new_size;
	else
		change = new_size - size;

	/* Resize the pane. */
	layout_resize_pane(wp, type, change);
}

/* Resize a single pane within the layout. */
void
layout_resize_pane(struct window_pane *wp, enum layout_type type, int change)
{
	struct layout_cell     *lc, *lcparent;
	int			needed, size;

	lc = wp->layout_cell;

	/* Find next parent of the same type. */
	lcparent = lc->parent;
	while (lcparent != NULL && lcparent->type != type) {
		lc = lcparent;
		lcparent = lc->parent;
	}
	if (lcparent == NULL)
		return;

	/* If this is the last cell, move back one. */
	if (lc == TAILQ_LAST(&lcparent->cells, layout_cells))
		lc = TAILQ_PREV(lc, layout_cells, entry);

	/* Grow or shrink the cell. */
	needed = change;
	while (needed != 0) {
		if (change > 0) {
			size = layout_resize_pane_grow(lc, type, needed);
			needed -= size;
		} else {
			size = layout_resize_pane_shrink(lc, type, needed);
			needed += size;
		}

		if (size == 0)	/* no more change possible */
			break;
	}

	/* Fix cell offsets. */
	layout_fix_offsets(wp->window->layout_root);
	layout_fix_panes(wp->window, wp->window->sx, wp->window->sy);
	notify_window_layout_changed(wp->window);
}

/* Helper function to grow pane. */
static int
layout_resize_pane_grow(struct layout_cell *lc, enum layout_type type,
    int needed)
{
	struct layout_cell	*lcadd, *lcremove;
	u_int			 size;

	/* Growing. Always add to the current cell. */
	lcadd = lc;

	/* Look towards the tail for a suitable cell for reduction. */
	lcremove = TAILQ_NEXT(lc, entry);
	while (lcremove != NULL) {
		size = layout_resize_check(lcremove, type);
		if (size > 0)
			break;
		lcremove = TAILQ_NEXT(lcremove, entry);
	}

	/* If none found, look towards the head. */
	if (lcremove == NULL) {
		lcremove = TAILQ_PREV(lc, layout_cells, entry);
		while (lcremove != NULL) {
			size = layout_resize_check(lcremove, type);
			if (size > 0)
				break;
			lcremove = TAILQ_PREV(lcremove, layout_cells, entry);
		}
		if (lcremove == NULL)
			return (0);
	}

	/* Change the cells. */
	if (size > (u_int) needed)
		size = needed;
	layout_resize_adjust(lcadd, type, size);
	layout_resize_adjust(lcremove, type, -size);
	return (size);
}

/* Helper function to shrink pane. */
static int
layout_resize_pane_shrink(struct layout_cell *lc, enum layout_type type,
    int needed)
{
	struct layout_cell	*lcadd, *lcremove;
	u_int			 size;

	/* Shrinking. Find cell to remove from by walking towards head. */
	lcremove = lc;
	do {
		size = layout_resize_check(lcremove, type);
		if (size != 0)
			break;
		lcremove = TAILQ_PREV(lcremove, layout_cells, entry);
	} while (lcremove != NULL);
	if (lcremove == NULL)
		return (0);

	/* And add onto the next cell (from the original cell). */
	lcadd = TAILQ_NEXT(lc, entry);
	if (lcadd == NULL)
		return (0);

	/* Change the cells. */
	if (size > (u_int) -needed)
		size = -needed;
	layout_resize_adjust(lcadd, type, size);
	layout_resize_adjust(lcremove, type, -size);
	return (size);
}

/* Assign window pane to newly split cell. */
void
layout_assign_pane(struct layout_cell *lc, struct window_pane *wp)
{
	layout_make_leaf(lc, wp);
	layout_fix_panes(wp->window, wp->window->sx, wp->window->sy);
}

/*
 * Split a pane into two. size is a hint, or -1 for default half/half
 * split. This must be followed by layout_assign_pane before much else happens!
 **/
struct layout_cell *
layout_split_pane(struct window_pane *wp, enum layout_type type, int size,
    int insert_before)
{
	struct layout_cell     *lc, *lcparent, *lcnew, *lc1, *lc2;
	u_int			sx, sy, xoff, yoff, size1, size2;

	lc = wp->layout_cell;

	/* Copy the old cell size. */
	sx = lc->sx;
	sy = lc->sy;
	xoff = lc->xoff;
	yoff = lc->yoff;

	/* Check there is enough space for the two new panes. */
	switch (type) {
	case LAYOUT_LEFTRIGHT:
		if (sx < PANE_MINIMUM * 2 + 1)
			return (NULL);
		break;
	case LAYOUT_TOPBOTTOM:
		if (sy < PANE_MINIMUM * 2 + 1)
			return (NULL);
		break;
	default:
		fatalx("bad layout type");
	}

	if (lc->parent != NULL && lc->parent->type == type) {
		/*
		 * If the parent exists and is of the same type as the split,
		 * create a new cell and insert it after this one.
		 */

		/* Create the new child cell. */
		lcparent = lc->parent;
		lcnew = layout_create_cell(lcparent);
		if (insert_before)
			TAILQ_INSERT_BEFORE(lc, lcnew, entry);
		else
			TAILQ_INSERT_AFTER(&lcparent->cells, lc, lcnew, entry);
	} else {
		/*
		 * Otherwise create a new parent and insert it.
		 */

		/* Create and insert the replacement parent. */
		lcparent = layout_create_cell(lc->parent);
		layout_make_node(lcparent, type);
		layout_set_size(lcparent, sx, sy, xoff, yoff);
		if (lc->parent == NULL)
			wp->window->layout_root = lcparent;
		else
			TAILQ_REPLACE(&lc->parent->cells, lc, lcparent, entry);

		/* Insert the old cell. */
		lc->parent = lcparent;
		TAILQ_INSERT_HEAD(&lcparent->cells, lc, entry);

		/* Create the new child cell. */
		lcnew = layout_create_cell(lcparent);
		if (insert_before)
			TAILQ_INSERT_HEAD(&lcparent->cells, lcnew, entry);
		else
			TAILQ_INSERT_TAIL(&lcparent->cells, lcnew, entry);
	}
	if (insert_before) {
		lc1 = lcnew;
		lc2 = lc;
	} else {
		lc1 = lc;
		lc2 = lcnew;
	}

	/* Set new cell sizes.  size is the target size or -1 for middle split,
	 * size1 is the size of the top/left and size2 the bottom/right.
	 */
	switch (type) {
	case LAYOUT_LEFTRIGHT:
		if (size < 0)
			size2 = ((sx + 1) / 2) - 1;
		else if (insert_before)
			size2 = sx - size - 1;
		else
			size2 = size;
		if (size2 < PANE_MINIMUM)
			size2 = PANE_MINIMUM;
		else if (size2 > sx - 2)
			size2 = sx - 2;
		size1 = sx - 1 - size2;
		layout_set_size(lc1, size1, sy, xoff, yoff);
		layout_set_size(lc2, size2, sy, xoff + lc1->sx + 1, yoff);
		break;
	case LAYOUT_TOPBOTTOM:
		if (size < 0)
			size2 = ((sy + 1) / 2) - 1;
		else if (insert_before)
			size2 = sy - size - 1;
		else
			size2 = size;
		if (size2 < PANE_MINIMUM)
			size2 = PANE_MINIMUM;
		else if (size2 > sy - 2)
			size2 = sy - 2;
		size1 = sy - 1 - size2;
		layout_set_size(lc1, sx, size1, xoff, yoff);
		layout_set_size(lc2, sx, size2, xoff, yoff + lc1->sy + 1);
		break;
	default:
		fatalx("bad layout type");
	}

	/* Assign the panes. */
	layout_make_leaf(lc, wp);

	return (lcnew);
}

/* Destroy the cell associated with a pane. */
void
layout_close_pane(struct window_pane *wp)
{
	/* Remove the cell. */
	layout_destroy_cell(wp->layout_cell, &wp->window->layout_root);

	/* Fix pane offsets and sizes. */
	if (wp->window->layout_root != NULL) {
		layout_fix_offsets(wp->window->layout_root);
		layout_fix_panes(wp->window, wp->window->sx, wp->window->sy);
	}
	notify_window_layout_changed(wp->window);
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: layout.c,v 1.27 2016/04/29 15:00:48 nicm Exp $ */
2
3			/*
4			* Copyright (c) 2009 Nicholas Marriott <nicholas.marriott@gmail.com>
5			*
6			* Permission to use, copy, modify, and distribute this software for any
7			* purpose with or without fee is hereby granted, provided that the above
8			* copyright notice and this permission notice appear in all copies.
9			*
10			* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11			* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12			* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13			* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14			* WHATSOEVER RESULTING FROM LOSS OF MIND, USE, DATA OR PROFITS, WHETHER
15			* IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
16			* OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17			*/
18
19			#include <sys/types.h>
20
21			#include <stdlib.h>
22
23			#include "tmux.h"
24
25			/*
26			* The window layout is a tree of cells each of which can be one of: a
27			* left-right container for a list of cells, a top-bottom container for a list
28			* of cells, or a container for a window pane.
29			*
30			* Each window has a pointer to the root of its layout tree (containing its
31			* panes), every pane has a pointer back to the cell containing it, and each
32			* cell a pointer to its parent cell.
33			*/
34
35			static int layout_resize_pane_grow(struct layout_cell *, enum layout_type,
36			int);
37			static int layout_resize_pane_shrink(struct layout_cell *,
38			enum layout_type, int);
39			static int layout_need_status(struct layout_cell *, int);
40
41			struct layout_cell *
42			layout_create_cell(struct layout_cell *lcparent)
43			{
44			struct layout_cell *lc;
45
46			lc = xmalloc(sizeof *lc);
47			lc->type = LAYOUT_WINDOWPANE;
48			lc->parent = lcparent;
49
50			TAILQ_INIT(&lc->cells);
51
52			lc->sx = UINT_MAX;
53			lc->sy = UINT_MAX;
54
55			lc->xoff = UINT_MAX;
56			lc->yoff = UINT_MAX;
57
58			lc->wp = NULL;
59
60			return (lc);
61			}
62
63			void
64			layout_free_cell(struct layout_cell *lc)
65			{
66			struct layout_cell *lcchild;
67
68			switch (lc->type) {
69			case LAYOUT_LEFTRIGHT:
70			case LAYOUT_TOPBOTTOM:
71			while (!TAILQ_EMPTY(&lc->cells)) {
72			lcchild = TAILQ_FIRST(&lc->cells);
73			TAILQ_REMOVE(&lc->cells, lcchild, entry);
74			layout_free_cell(lcchild);
75			}
76			break;
77			case LAYOUT_WINDOWPANE:
78			if (lc->wp != NULL)
79			lc->wp->layout_cell = NULL;
80			break;
81			}
82
83			free(lc);
84			}
85
86			void
87			layout_print_cell(struct layout_cell lc, const char hdr, u_int n)
88			{
89			struct layout_cell *lcchild;
90
91			log_debug("%s:%*s%p type %u [parent %p] wp=%p [%u,%u %ux%u]", hdr, n,
92			" ", lc, lc->type, lc->parent, lc->wp, lc->xoff, lc->yoff, lc->sx,
93			lc->sy);
94			switch (lc->type) {
95			case LAYOUT_LEFTRIGHT:
96			case LAYOUT_TOPBOTTOM:
97			TAILQ_FOREACH(lcchild, &lc->cells, entry)
98			layout_print_cell(lcchild, hdr, n + 1);
99			break;
100			case LAYOUT_WINDOWPANE:
101			break;
102			}
103			}
104
105			void
106			layout_set_size(struct layout_cell *lc, u_int sx, u_int sy, u_int xoff,
107			u_int yoff)
108			{
109			lc->sx = sx;
110			lc->sy = sy;
111
112			lc->xoff = xoff;
113			lc->yoff = yoff;
114			}
115
116			void
117			layout_make_leaf(struct layout_cell lc, struct window_pane wp)
118			{
119			lc->type = LAYOUT_WINDOWPANE;
120
121			TAILQ_INIT(&lc->cells);
122
123			wp->layout_cell = lc;
124			lc->wp = wp;
125			}
126
127			void
128			layout_make_node(struct layout_cell *lc, enum layout_type type)
129			{
130			if (type == LAYOUT_WINDOWPANE)
131			fatalx("bad layout type");
132			lc->type = type;
133
134			TAILQ_INIT(&lc->cells);
135
136			if (lc->wp != NULL)
137			lc->wp->layout_cell = NULL;
138			lc->wp = NULL;
139			}
140
141			/* Fix cell offsets based on their sizes. */
142			void
143			layout_fix_offsets(struct layout_cell *lc)
144			{
145			struct layout_cell *lcchild;
146			u_int xoff, yoff;
147
148			if (lc->type == LAYOUT_LEFTRIGHT) {
149			xoff = lc->xoff;
150			TAILQ_FOREACH(lcchild, &lc->cells, entry) {
151			lcchild->xoff = xoff;
152			lcchild->yoff = lc->yoff;
153			if (lcchild->type != LAYOUT_WINDOWPANE)
154			layout_fix_offsets(lcchild);
155			xoff += lcchild->sx + 1;
156			}
157			} else {
158			yoff = lc->yoff;
159			TAILQ_FOREACH(lcchild, &lc->cells, entry) {
160			lcchild->xoff = lc->xoff;
161			lcchild->yoff = yoff;
162			if (lcchild->type != LAYOUT_WINDOWPANE)
163			layout_fix_offsets(lcchild);
164			yoff += lcchild->sy + 1;
165			}
166			}
167			}
168
169			/*
170			* Returns 1 if we need to reserve space for the pane status line. This is the
171			* case for the most upper panes only.
172			*/
173			static int
174			layout_need_status(struct layout_cell *lc, int at_top)
175			{
176			struct layout_cell *first_lc;
177
178			if (lc->parent) {
179			if (lc->parent->type == LAYOUT_LEFTRIGHT)
180			return (layout_need_status(lc->parent, at_top));
181
182			if (at_top)
183			first_lc = TAILQ_FIRST(&lc->parent->cells);
184			else
185			first_lc = TAILQ_LAST(&lc->parent->cells,layout_cells);
186			if (lc == first_lc)
187			return (layout_need_status(lc->parent, at_top));
188			return (0);
189			}
190			return (1);
191			}
192
193			/* Update pane offsets and sizes based on their cells. */
194			void
195			layout_fix_panes(struct window *w, u_int wsx, u_int wsy)
196			{
197			struct window_pane *wp;
198			struct layout_cell *lc;
199			u_int sx, sy;
200			int shift, status, at_top;
201
202			status = options_get_number(w->options, "pane-border-status");
203			at_top = (status == 1);
204			TAILQ_FOREACH(wp, &w->panes, entry) {
205			if ((lc = wp->layout_cell) == NULL)
206			continue;
207
208			if (status != 0)
209			shift = layout_need_status(lc, at_top);
210			else
211			shift = 0;
212
213			wp->xoff = lc->xoff;
214			wp->yoff = lc->yoff;
215
216			if (shift && at_top)
217			wp->yoff += 1;
218
219			/*
220			* Layout cells are limited by the smallest size of other cells
221			* within the same row or column; if this isn't the case
222			* resizing becomes difficult.
223			*
224			* However, panes do not have to take up their entire cell, so
225			* they can be cropped to the window edge if the layout
226			* overflows and they are partly visible.
227			*
228			* This stops cells being hidden unnecessarily.
229			*/
230
231			/*
232			* Work out the horizontal size. If the pane is actually
233			* outside the window or the entire pane is already visible,
234			* don't crop.
235			*/
236			if (lc->xoff >= wsx \|\| lc->xoff + lc->sx < wsx)
237			sx = lc->sx;
238			else {
239			sx = wsx - lc->xoff;
240			if (sx < 1)
241			sx = lc->sx;
242			}
243
244			/*
245			* Similarly for the vertical size; the minimum vertical size
246			* is two because scroll regions cannot be one line.
247			*/
248			if (lc->yoff >= wsy \|\| lc->yoff + lc->sy < wsy)
249			sy = lc->sy;
250			else {
251			sy = wsy - lc->yoff;
252			if (sy < 2)
253			sy = lc->sy;
254			}
255
256			if (shift)
257			sy -= 1;
258
259			window_pane_resize(wp, sx, sy);
260			}
261			}
262
263			/* Count the number of available cells in a layout. */
264			u_int
265			layout_count_cells(struct layout_cell *lc)
266			{
267			struct layout_cell *lcchild;
268			u_int n;
269
270			switch (lc->type) {
271			case LAYOUT_WINDOWPANE:
272			return (1);
273			case LAYOUT_LEFTRIGHT:
274			case LAYOUT_TOPBOTTOM:
275			n = 0;
276			TAILQ_FOREACH(lcchild, &lc->cells, entry)
277			n += layout_count_cells(lcchild);
278			return (n);
279			default:
280			fatalx("bad layout type");
281			}
282			}
283
284			/* Calculate how much size is available to be removed from a cell. */
285			u_int
286			layout_resize_check(struct layout_cell *lc, enum layout_type type)
287			{
288			struct layout_cell *lcchild;
289			u_int available, minimum;
290
291			if (lc->type == LAYOUT_WINDOWPANE) {
292			/* Space available in this cell only. */
293			if (type == LAYOUT_LEFTRIGHT)
294			available = lc->sx;
295			else
296			available = lc->sy;
297
298			if (available > PANE_MINIMUM)
299			available -= PANE_MINIMUM;
300			else
301			available = 0;
302			} else if (lc->type == type) {
303			/* Same type: total of available space in all child cells. */
304			available = 0;
305			TAILQ_FOREACH(lcchild, &lc->cells, entry)
306			available += layout_resize_check(lcchild, type);
307			} else {
308			/* Different type: minimum of available space in child cells. */
309			minimum = UINT_MAX;
310			TAILQ_FOREACH(lcchild, &lc->cells, entry) {
311			available = layout_resize_check(lcchild, type);
312			if (available < minimum)
313			minimum = available;
314			}
315			available = minimum;
316			}
317
318			return (available);
319			}
320
321			/*
322			* Adjust cell size evenly, including altering its children. This function
323			* expects the change to have already been bounded to the space available.
324			*/
325			void
326			layout_resize_adjust(struct layout_cell *lc, enum layout_type type, int change)
327			{
328			struct layout_cell *lcchild;
329
330			/* Adjust the cell size. */
331			if (type == LAYOUT_LEFTRIGHT)
332			lc->sx += change;
333			else
334			lc->sy += change;
335
336			/* If this is a leaf cell, that is all that is necessary. */
337			if (type == LAYOUT_WINDOWPANE)
338			return;
339
340			/* Child cell runs in a different direction. */
341			if (lc->type != type) {
342			TAILQ_FOREACH(lcchild, &lc->cells, entry)
343			layout_resize_adjust(lcchild, type, change);
344			return;
345			}
346
347			/*
348			* Child cell runs in the same direction. Adjust each child equally
349			* until no further change is possible.
350			*/
351			while (change != 0) {
352			TAILQ_FOREACH(lcchild, &lc->cells, entry) {
353			if (change == 0)
354			break;
355			if (change > 0) {
356			layout_resize_adjust(lcchild, type, 1);
357			change--;
358			continue;
359			}
360			if (layout_resize_check(lcchild, type) > 0) {
361			layout_resize_adjust(lcchild, type, -1);
362			change++;
363			}
364			}
365			}
366			}
367
368			/* Destroy a cell and redistribute the space. */
369			void
370			layout_destroy_cell(struct layout_cell lc, struct layout_cell *lcroot)
371			{
372			struct layout_cell lcother, lcparent;
373
374			/*
375			* If no parent, this is the last pane so window close is imminent and
376			* there is no need to resize anything.
377			*/
378			lcparent = lc->parent;
379			if (lcparent == NULL) {
380			layout_free_cell(lc);
381			*lcroot = NULL;
382			return;
383			}
384
385			/* Merge the space into the previous or next cell. */
386			if (lc == TAILQ_FIRST(&lcparent->cells))
387			lcother = TAILQ_NEXT(lc, entry);
388			else
389			lcother = TAILQ_PREV(lc, layout_cells, entry);
390			if (lcparent->type == LAYOUT_LEFTRIGHT)
391			layout_resize_adjust(lcother, lcparent->type, lc->sx + 1);
392			else
393			layout_resize_adjust(lcother, lcparent->type, lc->sy + 1);
394
395			/* Remove this from the parent's list. */
396			TAILQ_REMOVE(&lcparent->cells, lc, entry);
397			layout_free_cell(lc);
398
399			/*
400			* If the parent now has one cell, remove the parent from the tree and
401			* replace it by that cell.
402			*/
403			lc = TAILQ_FIRST(&lcparent->cells);
404			if (TAILQ_NEXT(lc, entry) == NULL) {
405			TAILQ_REMOVE(&lcparent->cells, lc, entry);
406
407			lc->parent = lcparent->parent;
408			if (lc->parent == NULL) {
409			lc->xoff = 0; lc->yoff = 0;
410			*lcroot = lc;
411			} else
412			TAILQ_REPLACE(&lc->parent->cells, lcparent, lc, entry);
413
414			layout_free_cell(lcparent);
415			}
416			}
417
418			void
419			layout_init(struct window w, struct window_pane wp)
420			{
421			struct layout_cell *lc;
422
423			lc = w->layout_root = layout_create_cell(NULL);
424			layout_set_size(lc, w->sx, w->sy, 0, 0);
425			layout_make_leaf(lc, wp);
426
427			layout_fix_panes(w, w->sx, w->sy);
428			}
429
430			void
431			layout_free(struct window *w)
432			{
433			layout_free_cell(w->layout_root);
434			}
435
436			/* Resize the entire layout after window resize. */
437			void
438			layout_resize(struct window *w, u_int sx, u_int sy)
439			{
440			struct layout_cell *lc = w->layout_root;
441			int xlimit, ylimit, xchange, ychange;
442
443			/*
444			* Adjust horizontally. Do not attempt to reduce the layout lower than
445			* the minimum (more than the amount returned by layout_resize_check).
446			*
447			* This can mean that the window size is smaller than the total layout
448			* size: redrawing this is handled at a higher level, but it does leave
449			* a problem with growing the window size here: if the current size is
450			* < the minimum, growing proportionately by adding to each pane is
451			* wrong as it would keep the layout size larger than the window size.
452			* Instead, spread the difference between the minimum and the new size
453			* out proportionately - this should leave the layout fitting the new
454			* window size.
455			*/
456			xchange = sx - w->sx;
457			xlimit = layout_resize_check(lc, LAYOUT_LEFTRIGHT);
458			if (xchange < 0 && xchange < -xlimit)
459			xchange = -xlimit;
460			if (xlimit == 0) {
461			if (sx <= lc->sx) /* lc->sx is minimum possible */
462			xchange = 0;
463			else
464			xchange = sx - lc->sx;
465			}
466			if (xchange != 0)
467			layout_resize_adjust(lc, LAYOUT_LEFTRIGHT, xchange);
468
469			/* Adjust vertically in a similar fashion. */
470			ychange = sy - w->sy;
471			ylimit = layout_resize_check(lc, LAYOUT_TOPBOTTOM);
472			if (ychange < 0 && ychange < -ylimit)
473			ychange = -ylimit;
474			if (ylimit == 0) {
475			if (sy <= lc->sy) /* lc->sy is minimum possible */
476			ychange = 0;
477			else
478			ychange = sy - lc->sy;
479			}
480			if (ychange != 0)
481			layout_resize_adjust(lc, LAYOUT_TOPBOTTOM, ychange);
482
483			/* Fix cell offsets. */
484			layout_fix_offsets(lc);
485			layout_fix_panes(w, sx, sy);
486			}
487
488			/* Resize a pane to an absolute size. */
489			void
490			layout_resize_pane_to(struct window_pane *wp, enum layout_type type,
491			u_int new_size)
492			{
493			struct layout_cell lc, lcparent;
494			int change, size;
495
496			lc = wp->layout_cell;
497
498			/* Find next parent of the same type. */
499			lcparent = lc->parent;
500			while (lcparent != NULL && lcparent->type != type) {
501			lc = lcparent;
502			lcparent = lc->parent;
503			}
504			if (lcparent == NULL)
505			return;
506
507			/* Work out the size adjustment. */
508			if (type == LAYOUT_LEFTRIGHT)
509			size = lc->sx;
510			else
511			size = lc->sy;
512			if (lc == TAILQ_LAST(&lcparent->cells, layout_cells))
513			change = size - new_size;
514			else
515			change = new_size - size;
516
517			/* Resize the pane. */
518			layout_resize_pane(wp, type, change);
519			}
520
521			/* Resize a single pane within the layout. */
522			void
523			layout_resize_pane(struct window_pane *wp, enum layout_type type, int change)
524			{
525			struct layout_cell lc, lcparent;
526			int needed, size;
527
528			lc = wp->layout_cell;
529
530			/* Find next parent of the same type. */
531			lcparent = lc->parent;
532			while (lcparent != NULL && lcparent->type != type) {
533			lc = lcparent;
534			lcparent = lc->parent;
535			}
536			if (lcparent == NULL)
537			return;
538
539			/* If this is the last cell, move back one. */
540			if (lc == TAILQ_LAST(&lcparent->cells, layout_cells))
541			lc = TAILQ_PREV(lc, layout_cells, entry);
542
543			/* Grow or shrink the cell. */
544			needed = change;
545			while (needed != 0) {
546			if (change > 0) {
547			size = layout_resize_pane_grow(lc, type, needed);
548			needed -= size;
549			} else {
550			size = layout_resize_pane_shrink(lc, type, needed);
551			needed += size;
552			}
553
554			if (size == 0) /* no more change possible */
555			break;
556			}
557
558			/* Fix cell offsets. */
559			layout_fix_offsets(wp->window->layout_root);
560			layout_fix_panes(wp->window, wp->window->sx, wp->window->sy);
561			notify_window_layout_changed(wp->window);
562			}
563
564			/* Helper function to grow pane. */
565			static int
566			layout_resize_pane_grow(struct layout_cell *lc, enum layout_type type,
567			int needed)
568			{
569			struct layout_cell lcadd, lcremove;
570			u_int size;
571
572			/* Growing. Always add to the current cell. */
573			lcadd = lc;
574
575			/* Look towards the tail for a suitable cell for reduction. */
576			lcremove = TAILQ_NEXT(lc, entry);
577			while (lcremove != NULL) {
578			size = layout_resize_check(lcremove, type);
579			if (size > 0)
580			break;
581			lcremove = TAILQ_NEXT(lcremove, entry);
582			}
583
584			/* If none found, look towards the head. */
585			if (lcremove == NULL) {
586			lcremove = TAILQ_PREV(lc, layout_cells, entry);
587			while (lcremove != NULL) {
588			size = layout_resize_check(lcremove, type);
589			if (size > 0)
590			break;
591			lcremove = TAILQ_PREV(lcremove, layout_cells, entry);
592			}
593			if (lcremove == NULL)
594			return (0);
595			}
596
597			/* Change the cells. */
598			if (size > (u_int) needed)
599			size = needed;
600			layout_resize_adjust(lcadd, type, size);
601			layout_resize_adjust(lcremove, type, -size);
602			return (size);
603			}
604
605			/* Helper function to shrink pane. */
606			static int
607			layout_resize_pane_shrink(struct layout_cell *lc, enum layout_type type,
608			int needed)
609			{
610			struct layout_cell lcadd, lcremove;
611			u_int size;
612
613			/* Shrinking. Find cell to remove from by walking towards head. */
614			lcremove = lc;
615			do {
616			size = layout_resize_check(lcremove, type);
617			if (size != 0)
618			break;
619			lcremove = TAILQ_PREV(lcremove, layout_cells, entry);
620			} while (lcremove != NULL);
621			if (lcremove == NULL)
622			return (0);
623
624			/* And add onto the next cell (from the original cell). */
625			lcadd = TAILQ_NEXT(lc, entry);
626			if (lcadd == NULL)
627			return (0);
628
629			/* Change the cells. */
630			if (size > (u_int) -needed)
631			size = -needed;
632			layout_resize_adjust(lcadd, type, size);
633			layout_resize_adjust(lcremove, type, -size);
634			return (size);
635			}
636
637			/* Assign window pane to newly split cell. */
638			void
639			layout_assign_pane(struct layout_cell lc, struct window_pane wp)
640			{
641			layout_make_leaf(lc, wp);
642			layout_fix_panes(wp->window, wp->window->sx, wp->window->sy);
643			}
644
645			/*
646			* Split a pane into two. size is a hint, or -1 for default half/half
647			* split. This must be followed by layout_assign_pane before much else happens!
648			**/
649			struct layout_cell *
650			layout_split_pane(struct window_pane *wp, enum layout_type type, int size,
651			int insert_before)
652			{
653			struct layout_cell lc, lcparent, lcnew, lc1, *lc2;
654			u_int sx, sy, xoff, yoff, size1, size2;
655
656			lc = wp->layout_cell;
657
658			/* Copy the old cell size. */
659			sx = lc->sx;
660			sy = lc->sy;
661			xoff = lc->xoff;
662			yoff = lc->yoff;
663
664			/* Check there is enough space for the two new panes. */
665			switch (type) {
666			case LAYOUT_LEFTRIGHT:
667			if (sx < PANE_MINIMUM * 2 + 1)
668			return (NULL);
669			break;
670			case LAYOUT_TOPBOTTOM:
671			if (sy < PANE_MINIMUM * 2 + 1)
672			return (NULL);
673			break;
674			default:
675			fatalx("bad layout type");
676			}
677
678			if (lc->parent != NULL && lc->parent->type == type) {
679			/*
680			* If the parent exists and is of the same type as the split,
681			* create a new cell and insert it after this one.
682			*/
683
684			/* Create the new child cell. */
685			lcparent = lc->parent;
686			lcnew = layout_create_cell(lcparent);
687			if (insert_before)
688			TAILQ_INSERT_BEFORE(lc, lcnew, entry);
689			else
690			TAILQ_INSERT_AFTER(&lcparent->cells, lc, lcnew, entry);
691			} else {
692			/*
693			* Otherwise create a new parent and insert it.
694			*/
695
696			/* Create and insert the replacement parent. */
697			lcparent = layout_create_cell(lc->parent);
698			layout_make_node(lcparent, type);
699			layout_set_size(lcparent, sx, sy, xoff, yoff);
700			if (lc->parent == NULL)
701			wp->window->layout_root = lcparent;
702			else
703			TAILQ_REPLACE(&lc->parent->cells, lc, lcparent, entry);
704
705			/* Insert the old cell. */
706			lc->parent = lcparent;
707			TAILQ_INSERT_HEAD(&lcparent->cells, lc, entry);
708
709			/* Create the new child cell. */
710			lcnew = layout_create_cell(lcparent);
711			if (insert_before)
712			TAILQ_INSERT_HEAD(&lcparent->cells, lcnew, entry);
713			else
714			TAILQ_INSERT_TAIL(&lcparent->cells, lcnew, entry);
715			}
716			if (insert_before) {
717			lc1 = lcnew;
718			lc2 = lc;
719			} else {
720			lc1 = lc;
721			lc2 = lcnew;
722			}
723
724			/* Set new cell sizes. size is the target size or -1 for middle split,
725			* size1 is the size of the top/left and size2 the bottom/right.
726			*/
727			switch (type) {
728			case LAYOUT_LEFTRIGHT:
729			if (size < 0)
730			size2 = ((sx + 1) / 2) - 1;
731			else if (insert_before)
732			size2 = sx - size - 1;
733			else
734			size2 = size;
735			if (size2 < PANE_MINIMUM)
736			size2 = PANE_MINIMUM;
737			else if (size2 > sx - 2)
738			size2 = sx - 2;
739			size1 = sx - 1 - size2;
740			layout_set_size(lc1, size1, sy, xoff, yoff);
741			layout_set_size(lc2, size2, sy, xoff + lc1->sx + 1, yoff);
742			break;
743			case LAYOUT_TOPBOTTOM:
744			if (size < 0)
745			size2 = ((sy + 1) / 2) - 1;
746			else if (insert_before)
747			size2 = sy - size - 1;
748			else
749			size2 = size;
750			if (size2 < PANE_MINIMUM)
751			size2 = PANE_MINIMUM;
752			else if (size2 > sy - 2)
753			size2 = sy - 2;
754			size1 = sy - 1 - size2;
755			layout_set_size(lc1, sx, size1, xoff, yoff);
756			layout_set_size(lc2, sx, size2, xoff, yoff + lc1->sy + 1);
757			break;
758			default:
759			fatalx("bad layout type");
760			}
761
762			/* Assign the panes. */
763			layout_make_leaf(lc, wp);
764
765			return (lcnew);
766			}
767
768			/* Destroy the cell associated with a pane. */
769			void
770			layout_close_pane(struct window_pane *wp)
771			{
772			/* Remove the cell. */
773			layout_destroy_cell(wp->layout_cell, &wp->window->layout_root);
774
775			/* Fix pane offsets and sizes. */
776			if (wp->window->layout_root != NULL) {
777			layout_fix_offsets(wp->window->layout_root);
778			layout_fix_panes(wp->window, wp->window->sx, wp->window->sy);
779			}
780			notify_window_layout_changed(wp->window);
781			}