src/tree.c

   1 /* Copyright (c) 2012, Bastien Dejean
   2  * All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  * 1. Redistributions of source code must retain the above copyright notice, this
   8  *    list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright notice,
  10  *    this list of conditions and the following disclaimer in the documentation
  11  *    and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  15  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  16  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
  17  * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  18  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  19  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  20  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  21  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  22  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  23  */
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <stdbool.h>
  28 #include "bspwm.h"
  29 #include "desktop.h"
  30 #include "ewmh.h"
  31 #include "history.h"
  32 #include "monitor.h"
  33 #include "query.h"
  34 #include "geometry.h"
  35 #include "subscribe.h"
  36 #include "settings.h"
  37 #include "pointer.h"
  38 #include "stack.h"
  39 #include "window.h"
  40 #include "tree.h"
  41
  42 void arrange(monitor_t *m, desktop_t *d)
  43 {
  44         if (d->root == NULL) {
  45                 return;
  46         }
  47
  48         layout_t l = d->layout;
  49
  50         if (single_monocle && tiled_count(d->root) <= 1) {
  51                 l = LAYOUT_MONOCLE;
  52         }
  53
  54         xcb_rectangle_t rect = m->rectangle;
  55
  56         if (!paddingless_monocle || l != LAYOUT_MONOCLE) {
  57                 rect.x += m->padding.left + d->padding.left;
  58                 rect.y += m->padding.top + d->padding.top;
  59                 rect.width -= m->padding.left + d->padding.left + d->padding.right + m->padding.right;
  60                 rect.height -= m->padding.top + d->padding.top + d->padding.bottom + m->padding.bottom;
  61         }
  62
  63         if (!gapless_monocle || l != LAYOUT_MONOCLE) {
  64                 rect.x += d->window_gap;
  65                 rect.y += d->window_gap;
  66                 rect.width -= d->window_gap;
  67                 rect.height -= d->window_gap;
  68         }
  69
  70         apply_layout(m, d, d->root, l, rect, rect);
  71 }
  72
  73 void apply_layout(monitor_t *m, desktop_t *d, node_t *n, layout_t l, xcb_rectangle_t rect, xcb_rectangle_t root_rect)
  74 {
  75         if (n == NULL) {
  76                 return;
  77         }
  78
  79         n->rectangle = rect;
  80
  81         if (pointer_follows_focus && mon->desk->focus == n) {
  82                 xcb_rectangle_t r = rect;
  83                 r.width -= d->window_gap;
  84                 r.height -= d->window_gap;
  85                 center_pointer(r);
  86         }
  87
  88         if (n->presel != NULL) {
  89                 draw_presel_feedback(m, d, n);
  90         }
  91
  92         if (is_leaf(n)) {
  93
  94                 if (n->client == NULL) {
  95                         return;
  96                 }
  97
  98                 unsigned int bw;
  99                 if ((borderless_monocle && l == LAYOUT_MONOCLE && IS_TILED(n->client))
 100                     || n->client->state == STATE_FULLSCREEN) {
 101                         bw = 0;
 102                 } else {
 103                         bw = n->client->border_width;
 104                 }
 105
 106                 xcb_rectangle_t r;
 107                 xcb_rectangle_t cr = get_window_rectangle(n);
 108                 client_state_t s = n->client->state;
 109                 if (s == STATE_TILED || s == STATE_PSEUDO_TILED) {
 110                         int wg = (gapless_monocle && l == LAYOUT_MONOCLE ? 0 : d->window_gap);
 111                         /* tiled clients */
 112                         if (s == STATE_TILED) {
 113                                 r = rect;
 114                                 int bleed = wg + 2 * bw;
 115                                 r.width = (bleed < r.width ? r.width - bleed : 1);
 116                                 r.height = (bleed < r.height ? r.height - bleed : 1);
 117                         /* pseudo-tiled clients */
 118                         } else {
 119                                 r = n->client->floating_rectangle;
 120                                 if (center_pseudo_tiled) {
 121                                         r.x = rect.x - bw + (rect.width - wg - r.width) / 2;
 122                                         r.y = rect.y - bw + (rect.height - wg - r.height) / 2;
 123                                 } else {
 124                                         r.x = rect.x;
 125                                         r.y = rect.y;
 126                                 }
 127                         }
 128                         n->client->tiled_rectangle = r;
 129                 /* floating clients */
 130                 } else if (s == STATE_FLOATING) {
 131                         r = n->client->floating_rectangle;
 132                 /* fullscreen clients */
 133                 } else {
 134                         r = m->rectangle;
 135                         n->client->tiled_rectangle = r;
 136                 }
 137
 138                 apply_size_hints(n->client, &r.width, &r.height);
 139
 140                 if (!rect_eq(r, cr)) {
 141                         window_move_resize(n->id, r.x, r.y, r.width, r.height);
 142                         if (!grabbing) {
 143                                 put_status(SBSC_MASK_NODE_GEOMETRY, "node_geometry 0x%08X 0x%08X 0x%08X %ux%u+%i+%i\n", m->id, d->id, n->id, r.width, r.height, r.x, r.y);
 144                         }
 145                 }
 146
 147                 window_border_width(n->id, bw);
 148
 149         } else {
 150                 xcb_rectangle_t first_rect;
 151                 xcb_rectangle_t second_rect;
 152
 153                 if (l == LAYOUT_MONOCLE || n->first_child->vacant || n->second_child->vacant) {
 154                         first_rect = second_rect = rect;
 155                 } else {
 156                         unsigned int fence;
 157                         if (n->split_type == TYPE_VERTICAL) {
 158                                 fence = rect.width * n->split_ratio;
 159                                 if ((n->first_child->constraints.min_width + n->second_child->constraints.min_width) <= rect.width) {
 160                                         if (fence < n->first_child->constraints.min_width) {
 161                                                 fence = n->first_child->constraints.min_width;
 162                                                 n->split_ratio = (double) fence / (double) rect.width;
 163                                         } else if (fence > (uint16_t) (rect.width - n->second_child->constraints.min_width)) {
 164                                                 fence = (rect.width - n->second_child->constraints.min_width);
 165                                                 n->split_ratio = (double) fence / (double) rect.width;
 166                                         }
 167                                 }
 168                                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
 169                                 second_rect = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
 170                         } else {
 171                                 fence = rect.height * n->split_ratio;
 172                                 if ((n->first_child->constraints.min_height + n->second_child->constraints.min_height) <= rect.height) {
 173                                         if (fence < n->first_child->constraints.min_height) {
 174                                                 fence = n->first_child->constraints.min_height;
 175                                                 n->split_ratio = (double) fence / (double) rect.height;
 176                                         } else if (fence > (uint16_t) (rect.height - n->second_child->constraints.min_height)) {
 177                                                 fence = (rect.height - n->second_child->constraints.min_height);
 178                                                 n->split_ratio = (double) fence / (double) rect.height;
 179                                         }
 180                                 }
 181                                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
 182                                 second_rect = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
 183                         }
 184                 }
 185
 186                 apply_layout(m, d, n->first_child, l, first_rect, root_rect);
 187                 apply_layout(m, d, n->second_child, l, second_rect, root_rect);
 188         }
 189 }
 190
 191 presel_t *make_presel(void)
 192 {
 193         presel_t *p = calloc(1, sizeof(presel_t));
 194         p->split_dir = DIR_EAST;
 195         p->split_ratio = split_ratio;
 196         p->feedback = XCB_NONE;
 197         return p;
 198 }
 199
 200 void set_ratio(node_t *n, double rat)
 201 {
 202         if (n == NULL) {
 203                 return;
 204         }
 205
 206         n->split_ratio = rat;
 207 }
 208
 209 void presel_dir(monitor_t *m, desktop_t *d, node_t *n, direction_t dir)
 210 {
 211         if (n->presel == NULL) {
 212                 n->presel = make_presel();
 213         }
 214
 215         n->presel->split_dir = dir;
 216
 217         put_status(SBSC_MASK_NODE_PRESEL, "node_presel 0x%08X 0x%08X 0x%08X dir %s\n", m->id, d->id, n->id, SPLIT_DIR_STR(dir));
 218 }
 219
 220 void presel_ratio(monitor_t *m, desktop_t *d, node_t *n, double ratio)
 221 {
 222         if (n->presel == NULL) {
 223                 n->presel = make_presel();
 224         }
 225
 226         n->presel->split_ratio = ratio;
 227
 228         put_status(SBSC_MASK_NODE_PRESEL, "node_presel 0x%08X 0x%08X 0x%08X ratio %lf\n", m->id, d->id, n->id, ratio);
 229 }
 230
 231 void cancel_presel(monitor_t *m, desktop_t *d, node_t *n)
 232 {
 233         if (n->presel == NULL) {
 234                 return;
 235         }
 236
 237         if (n->presel->feedback != XCB_NONE) {
 238                 xcb_destroy_window(dpy, n->presel->feedback);
 239         }
 240
 241         free(n->presel);
 242         n->presel = NULL;
 243
 244         put_status(SBSC_MASK_NODE_PRESEL, "node_presel 0x%08X 0x%08X 0x%08X cancel\n", m->id, d->id, n->id);
 245 }
 246
 247 void cancel_presel_in(monitor_t *m, desktop_t *d, node_t *n)
 248 {
 249         if (n == NULL) {
 250                 return;
 251         }
 252         cancel_presel(m, d, n);
 253         cancel_presel_in(m, d, n->first_child);
 254         cancel_presel_in(m, d, n->second_child);
 255 }
 256
 257 node_t *find_public(desktop_t *d)
 258 {
 259         unsigned int b_manual_area = 0;
 260         unsigned int b_automatic_area = 0;
 261         node_t *b_manual = NULL;
 262         node_t *b_automatic = NULL;
 263         for (node_t *n = first_extrema(d->root); n != NULL; n = next_leaf(n, d->root)) {
 264                 if (n->vacant) {
 265                         continue;
 266                 }
 267                 unsigned int n_area = node_area(d, n);
 268                 if (n_area > b_manual_area && (n->presel != NULL || !n->private)) {
 269                         b_manual = n;
 270                         b_manual_area = n_area;
 271                 }
 272                 if (n_area > b_automatic_area &&
 273                     n->presel == NULL && !n->private && private_count(n->parent) == 0) {
 274                         b_automatic = n;
 275                         b_automatic_area = n_area;
 276                 }
 277         }
 278         if (b_automatic != NULL) {
 279                 return b_automatic;
 280         } else {
 281                 return b_manual;
 282         }
 283 }
 284
 285 node_t *insert_node(monitor_t *m, desktop_t *d, node_t *n, node_t *f)
 286 {
 287         if (d == NULL || n == NULL) {
 288                 return NULL;
 289         }
 290
 291         /* n: inserted node */
 292         /* c: new internal node */
 293         /* f: focus or insertion anchor */
 294         /* p: parent of focus */
 295         /* g: grand parent of focus */
 296
 297         if (f == NULL) {
 298                 f = d->root;
 299         }
 300
 301         if (f == NULL) {
 302                 d->root = n;
 303         } else if (IS_RECEPTACLE(f) && f->presel == NULL) {
 304                 node_t *p = f->parent;
 305                 if (p != NULL) {
 306                         if (is_first_child(f)) {
 307                                 p->first_child = n;
 308                         } else {
 309                                 p->second_child = n;
 310                         }
 311                 } else {
 312                         d->root = n;
 313                 }
 314                 n->parent = p;
 315                 free(f);
 316                 f = NULL;
 317         } else {
 318                 node_t *c = make_node(XCB_NONE);
 319                 node_t *p = f->parent;
 320                 if (f->presel == NULL && (f->private || private_count(f->parent) > 0)) {
 321                         node_t *k = find_public(d);
 322                         if (k != NULL) {
 323                                 f = k;
 324                                 p = f->parent;
 325                         }
 326                         if (f->presel == NULL && (f->private || private_count(f->parent) > 0)) {
 327                                 xcb_rectangle_t rect = get_rectangle(m, d, f);
 328                                 presel_dir(m, d, f, (rect.width >= rect.height ? DIR_EAST : DIR_SOUTH));
 329                         }
 330                 }
 331                 if (f->presel == NULL && p != NULL && p->vacant) {
 332                         f = p;
 333                         p = f->parent;
 334                 }
 335                 n->parent = c;
 336                 c->birth_rotation = f->birth_rotation;
 337                 if (f->presel == NULL) {
 338                         if (p == NULL) {
 339                                 if (initial_polarity == FIRST_CHILD) {
 340                                         c->first_child = n;
 341                                         c->second_child = f;
 342                                 } else {
 343                                         c->first_child = f;
 344                                         c->second_child = n;
 345                                 }
 346                                 if (m->rectangle.width > m->rectangle.height) {
 347                                         c->split_type = TYPE_VERTICAL;
 348                                 } else {
 349                                         c->split_type = TYPE_HORIZONTAL;
 350                                 }
 351                                 f->parent = c;
 352                                 d->root = c;
 353                         } else {
 354                                 node_t *g = p->parent;
 355                                 c->parent = g;
 356                                 if (g != NULL) {
 357                                         if (is_first_child(p)) {
 358                                                 g->first_child = c;
 359                                         } else {
 360                                                 g->second_child = c;
 361                                         }
 362                                 } else {
 363                                         d->root = c;
 364                                 }
 365                                 c->split_type = p->split_type;
 366                                 c->split_ratio = p->split_ratio;
 367                                 p->parent = c;
 368                                 int rot;
 369                                 if (is_first_child(f)) {
 370                                         c->first_child = n;
 371                                         c->second_child = p;
 372                                         rot = 90;
 373                                 } else {
 374                                         c->first_child = p;
 375                                         c->second_child = n;
 376                                         rot = 270;
 377                                 }
 378                                 n->birth_rotation = rot;
 379                                 if (!n->vacant) {
 380                                         rotate_tree(p, rot);
 381                                 }
 382                         }
 383                 } else {
 384                         if (p != NULL) {
 385                                 if (is_first_child(f)) {
 386                                         p->first_child = c;
 387                                 } else {
 388                                         p->second_child = c;
 389                                 }
 390                         }
 391                         c->split_ratio = f->presel->split_ratio;
 392                         c->parent = p;
 393                         f->parent = c;
 394                         f->birth_rotation = 0;
 395                         switch (f->presel->split_dir) {
 396                                 case DIR_WEST:
 397                                         c->split_type = TYPE_VERTICAL;
 398                                         c->first_child = n;
 399                                         c->second_child = f;
 400                                         break;
 401                                 case DIR_EAST:
 402                                         c->split_type = TYPE_VERTICAL;
 403                                         c->first_child = f;
 404                                         c->second_child = n;
 405                                         break;
 406                                 case DIR_NORTH:
 407                                         c->split_type = TYPE_HORIZONTAL;
 408                                         c->first_child = n;
 409                                         c->second_child = f;
 410                                         break;
 411                                 case DIR_SOUTH:
 412                                         c->split_type = TYPE_HORIZONTAL;
 413                                         c->first_child = f;
 414                                         c->second_child = n;
 415                                         break;
 416                         }
 417                         if (d->root == f) {
 418                                 d->root = c;
 419                         }
 420                         cancel_presel(m, d, f);
 421                 }
 422         }
 423
 424         propagate_flags_upward(m, d, n);
 425
 426         if (d->focus == NULL && is_focusable(n)) {
 427                 d->focus = n;
 428         }
 429
 430         return f;
 431 }
 432
 433 void insert_receptacle(monitor_t *m, desktop_t *d, node_t *n)
 434 {
 435         node_t *r = make_node(XCB_NONE);
 436         insert_node(m, d, r, n);
 437 }
 438
 439 bool activate_node(monitor_t *m, desktop_t *d, node_t *n)
 440 {
 441         if (n == NULL && d->root != NULL) {
 442                 n = history_last_node(d, NULL);
 443                 if (n == NULL) {
 444                         n = first_focusable_leaf(d->root);
 445                 }
 446         }
 447
 448         if (d == mon->desk || (n != NULL && !is_focusable(n))) {
 449                 return false;
 450         }
 451
 452         if (n != NULL) {
 453                 if (d->focus != NULL && n != d->focus) {
 454                         neutralize_occluding_windows(m, d, n);
 455                 }
 456                 stack(d, n, true);
 457                 if (d->focus != n) {
 458                         for (node_t *f = first_extrema(d->focus); f != NULL; f = next_leaf(f, d->focus)) {
 459                                 if (f->client != NULL && !is_descendant(f, n)) {
 460                                         window_draw_border(f->id, get_border_color(false, (m == mon)));
 461                                 }
 462                         }
 463                 }
 464                 draw_border(n, true, (m == mon));
 465         }
 466
 467         d->focus = n;
 468         history_add(m, d, n);
 469
 470         put_status(SBSC_MASK_REPORT);
 471
 472         if (n == NULL) {
 473                 return true;
 474         }
 475
 476         put_status(SBSC_MASK_NODE_ACTIVATE, "node_activate 0x%08X 0x%08X 0x%08X\n", m->id, d->id, n->id);
 477
 478         return true;
 479 }
 480
 481 void transfer_sticky_nodes(monitor_t *m, desktop_t *ds, desktop_t *dd, node_t *n)
 482 {
 483         if (n == NULL) {
 484                 return;
 485         } else if (n->sticky) {
 486                 transfer_node(m, ds, n, m, dd, dd->focus);
 487         } else {
 488                 /* we need references to the children because n might be freed after
 489                  * the first recursive call */
 490                 node_t *first_child = n->first_child;
 491                 node_t *second_child = n->second_child;
 492                 transfer_sticky_nodes(m, ds, dd, first_child);
 493                 transfer_sticky_nodes(m, ds, dd, second_child);
 494         }
 495 }
 496
 497 bool focus_node(monitor_t *m, desktop_t *d, node_t *n)
 498 {
 499         if (m == NULL) {
 500                 m = history_last_monitor(NULL);
 501                 if (m == NULL) {
 502                         m = mon_head;
 503                 }
 504         }
 505
 506         if (m == NULL) {
 507                 return false;
 508         }
 509
 510         if (d == NULL) {
 511                 d = history_last_desktop(m, NULL);
 512                 if (d == NULL) {
 513                         d = m->desk_head;
 514                 }
 515         }
 516
 517         if (d == NULL) {
 518                 return false;
 519         }
 520
 521         if (n == NULL && d->root != NULL) {
 522                 n = history_last_node(d, NULL);
 523                 if (n == NULL) {
 524                         n = first_focusable_leaf(d->root);
 525                 }
 526         }
 527
 528         if (n != NULL && !is_focusable(n)) {
 529                 return false;
 530         }
 531
 532         if ((mon != NULL && mon->desk != d) || n == NULL || n->client == NULL) {
 533                 clear_input_focus();
 534         }
 535
 536         if (m->sticky_count > 0 && d != m->desk) {
 537                 sticky_still = false;
 538                 transfer_sticky_nodes(m, m->desk, d, m->desk->root);
 539                 sticky_still = true;
 540                 if (n == NULL && d->focus != NULL) {
 541                         n = d->focus;
 542                 }
 543         }
 544
 545         if (d->focus != NULL && n != d->focus) {
 546                 neutralize_occluding_windows(m, d, n);
 547         }
 548
 549         if (n != NULL && n->client != NULL && n->client->urgent) {
 550                 set_urgent(m, d, n, false);
 551         }
 552
 553         if (mon != m) {
 554                 if (mon != NULL) {
 555                         for (desktop_t *e = mon->desk_head; e != NULL; e = e->next) {
 556                                 draw_border(e->focus, true, false);
 557                         }
 558                 }
 559                 for (desktop_t *e = m->desk_head; e != NULL; e = e->next) {
 560                         if (e == d) {
 561                                 continue;
 562                         }
 563                         draw_border(e->focus, true, true);
 564                 }
 565         }
 566
 567         if (d->focus != n) {
 568                 for (node_t *f = first_extrema(d->focus); f != NULL; f = next_leaf(f, d->focus)) {
 569                         if (f->client != NULL && !is_descendant(f, n)) {
 570                                 window_draw_border(f->id, get_border_color(false, true));
 571                         }
 572                 }
 573         }
 574
 575         draw_border(n, true, true);
 576
 577         focus_desktop(m, d);
 578
 579         d->focus = n;
 580         ewmh_update_active_window();
 581         history_add(m, d, n);
 582
 583         put_status(SBSC_MASK_REPORT);
 584
 585         if (n == NULL) {
 586                 if (focus_follows_pointer) {
 587                         update_motion_recorder();
 588                 }
 589                 return true;
 590         }
 591
 592         put_status(SBSC_MASK_NODE_FOCUS, "node_focus 0x%08X 0x%08X 0x%08X\n", m->id, d->id, n->id);
 593
 594         stack(d, n, true);
 595         set_input_focus(n);
 596
 597         if (pointer_follows_focus) {
 598                 center_pointer(get_rectangle(m, d, n));
 599         } else if (focus_follows_pointer) {
 600                 update_motion_recorder();
 601         }
 602
 603         return true;
 604 }
 605
 606 void hide_node(desktop_t *d, node_t *n)
 607 {
 608         if (n == NULL) {
 609                 return;
 610         } else {
 611                 if (!n->hidden) {
 612                         if (n->presel != NULL && d->layout != LAYOUT_MONOCLE) {
 613                                 window_hide(n->presel->feedback);
 614                         }
 615                         if (n->client != NULL) {
 616                                 window_hide(n->id);
 617                         }
 618                 }
 619                 if (n->client != NULL) {
 620                         n->client->shown = false;
 621                 }
 622                 hide_node(d, n->first_child);
 623                 hide_node(d, n->second_child);
 624         }
 625 }
 626
 627 void show_node(desktop_t *d, node_t *n)
 628 {
 629         if (n == NULL) {
 630                 return;
 631         } else {
 632                 if (!n->hidden) {
 633                         if (n->client != NULL) {
 634                                 window_show(n->id);
 635                         }
 636                         if (n->presel != NULL && d->layout != LAYOUT_MONOCLE) {
 637                                 window_show(n->presel->feedback);
 638                         }
 639                 }
 640                 if (n->client != NULL) {
 641                         n->client->shown = true;
 642                 }
 643                 show_node(d, n->first_child);
 644                 show_node(d, n->second_child);
 645         }
 646 }
 647
 648 node_t *make_node(uint32_t id)
 649 {
 650         if (id == XCB_NONE) {
 651                 id = xcb_generate_id(dpy);
 652         }
 653         node_t *n = calloc(1, sizeof(node_t));
 654         n->id = id;
 655         n->parent = n->first_child = n->second_child = NULL;
 656         n->vacant = n->hidden = n->sticky = n->private = n->locked = false;
 657         n->split_ratio = split_ratio;
 658         n->split_type = TYPE_VERTICAL;
 659         n->birth_rotation = 0;
 660         n->constraints = (constraints_t) {MIN_WIDTH, MIN_HEIGHT};
 661         n->presel = NULL;
 662         n->client = NULL;
 663         return n;
 664 }
 665
 666 client_t *make_client(void)
 667 {
 668         client_t *c = calloc(1, sizeof(client_t));
 669         c->state = c->last_state = STATE_TILED;
 670         c->layer = c->last_layer = LAYER_NORMAL;
 671         snprintf(c->class_name, sizeof(c->class_name), "%s", MISSING_VALUE);
 672         snprintf(c->instance_name, sizeof(c->instance_name), "%s", MISSING_VALUE);
 673         c->border_width = border_width;
 674         c->urgent = false;
 675         c->shown = false;
 676         c->wm_flags = 0;
 677         c->icccm_props.input_hint = true;
 678         c->icccm_props.take_focus = false;
 679         c->icccm_props.delete_window = false;
 680         c->size_hints.flags = 0;
 681         return c;
 682 }
 683
 684 void initialize_client(node_t *n)
 685 {
 686         xcb_window_t win = n->id;
 687         client_t *c = n->client;
 688         xcb_icccm_get_wm_protocols_reply_t protos;
 689         if (xcb_icccm_get_wm_protocols_reply(dpy, xcb_icccm_get_wm_protocols(dpy, win, ewmh->WM_PROTOCOLS), &protos, NULL) == 1) {
 690                 for (uint32_t i = 0; i < protos.atoms_len; i++) {
 691                         if (protos.atoms[i] == WM_TAKE_FOCUS) {
 692                                 c->icccm_props.take_focus = true;
 693                         } else if (protos.atoms[i] == WM_DELETE_WINDOW) {
 694                                 c->icccm_props.delete_window = true;
 695                         }
 696                 }
 697                 xcb_icccm_get_wm_protocols_reply_wipe(&protos);
 698         }
 699         xcb_ewmh_get_atoms_reply_t wm_state;
 700         if (xcb_ewmh_get_wm_state_reply(ewmh, xcb_ewmh_get_wm_state(ewmh, win), &wm_state, NULL) == 1) {
 701                 for (unsigned int i = 0; i < wm_state.atoms_len && i < MAX_WM_STATES; i++) {
 702 #define HANDLE_WM_STATE(s) \
 703                         if (wm_state.atoms[i] == ewmh->_NET_WM_STATE_##s) { \
 704                                 c->wm_flags |= WM_FLAG_##s; continue; \
 705                         }
 706                         HANDLE_WM_STATE(MODAL)
 707                         HANDLE_WM_STATE(STICKY)
 708                         HANDLE_WM_STATE(MAXIMIZED_VERT)
 709                         HANDLE_WM_STATE(MAXIMIZED_HORZ)
 710                         HANDLE_WM_STATE(SHADED)
 711                         HANDLE_WM_STATE(SKIP_TASKBAR)
 712                         HANDLE_WM_STATE(SKIP_PAGER)
 713                         HANDLE_WM_STATE(HIDDEN)
 714                         HANDLE_WM_STATE(FULLSCREEN)
 715                         HANDLE_WM_STATE(ABOVE)
 716                         HANDLE_WM_STATE(BELOW)
 717                         HANDLE_WM_STATE(DEMANDS_ATTENTION)
 718 #undef HANDLE_WM_STATE
 719                 }
 720                 xcb_ewmh_get_atoms_reply_wipe(&wm_state);
 721         }
 722         xcb_icccm_wm_hints_t hints;
 723         if (xcb_icccm_get_wm_hints_reply(dpy, xcb_icccm_get_wm_hints(dpy, win), &hints, NULL) == 1
 724                 && (hints.flags & XCB_ICCCM_WM_HINT_INPUT)) {
 725                 c->icccm_props.input_hint = hints.input;
 726         }
 727         xcb_icccm_get_wm_normal_hints_reply(dpy, xcb_icccm_get_wm_normal_hints(dpy, win), &c->size_hints, NULL);
 728 }
 729
 730 bool is_focusable(node_t *n)
 731 {
 732         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
 733                 if (f->client != NULL && !f->hidden) {
 734                         return true;
 735                 }
 736         }
 737         return false;
 738 }
 739
 740 bool is_leaf(node_t *n)
 741 {
 742         return (n != NULL && n->first_child == NULL && n->second_child == NULL);
 743 }
 744
 745 bool is_first_child(node_t *n)
 746 {
 747         return (n != NULL && n->parent != NULL && n->parent->first_child == n);
 748 }
 749
 750 bool is_second_child(node_t *n)
 751 {
 752         return (n != NULL && n->parent != NULL && n->parent->second_child == n);
 753 }
 754
 755 unsigned int clients_count_in(node_t *n)
 756 {
 757         if (n == NULL) {
 758                 return 0;
 759         } else {
 760                 return (n->client != NULL ? 1 : 0) +
 761                         clients_count_in(n->first_child) +
 762                         clients_count_in(n->second_child);
 763         }
 764 }
 765
 766 node_t *brother_tree(node_t *n)
 767 {
 768         if (n == NULL || n->parent == NULL) {
 769                 return NULL;
 770         }
 771         if (is_first_child(n)) {
 772                 return n->parent->second_child;
 773         } else {
 774                 return n->parent->first_child;
 775         }
 776 }
 777
 778 node_t *first_extrema(node_t *n)
 779 {
 780         if (n == NULL) {
 781                 return NULL;
 782         } else if (n->first_child == NULL) {
 783                 return n;
 784         } else {
 785                 return first_extrema(n->first_child);
 786         }
 787 }
 788
 789 node_t *second_extrema(node_t *n)
 790 {
 791         if (n == NULL) {
 792                 return NULL;
 793         } else if (n->second_child == NULL) {
 794                 return n;
 795         } else {
 796                 return second_extrema(n->second_child);
 797         }
 798 }
 799
 800 node_t *first_focusable_leaf(node_t *n)
 801 {
 802         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
 803                 if (f->client != NULL && !f->hidden) {
 804                         return f;
 805                 }
 806         }
 807         return NULL;
 808 }
 809
 810 node_t *next_leaf(node_t *n, node_t *r)
 811 {
 812         if (n == NULL) {
 813                 return NULL;
 814         }
 815         node_t *p = n;
 816         while (is_second_child(p) && p != r) {
 817                 p = p->parent;
 818         }
 819         if (p == r) {
 820                 return NULL;
 821         }
 822         return first_extrema(p->parent->second_child);
 823 }
 824
 825 node_t *prev_leaf(node_t *n, node_t *r)
 826 {
 827         if (n == NULL) {
 828                 return NULL;
 829         }
 830         node_t *p = n;
 831         while (is_first_child(p) && p != r) {
 832                 p = p->parent;
 833         }
 834         if (p == r) {
 835                 return NULL;
 836         }
 837         return second_extrema(p->parent->first_child);
 838 }
 839
 840 node_t *next_tiled_leaf(node_t *n, node_t *r)
 841 {
 842         node_t *next = next_leaf(n, r);
 843         if (next == NULL || (next->client != NULL && !next->vacant)) {
 844                 return next;
 845         } else {
 846                 return next_tiled_leaf(next, r);
 847         }
 848 }
 849
 850 node_t *prev_tiled_leaf(node_t *n, node_t *r)
 851 {
 852         node_t *prev = prev_leaf(n, r);
 853         if (prev == NULL || (prev->client != NULL && !prev->vacant)) {
 854                 return prev;
 855         } else {
 856                 return prev_tiled_leaf(prev, r);
 857         }
 858 }
 859
 860 /* Returns true if *b* is adjacent to *a* in the direction *dir* */
 861 bool is_adjacent(node_t *a, node_t *b, direction_t dir)
 862 {
 863         switch (dir) {
 864                 case DIR_EAST:
 865                         return (a->rectangle.x + a->rectangle.width) == b->rectangle.x;
 866                         break;
 867                 case DIR_SOUTH:
 868                         return (a->rectangle.y + a->rectangle.height) == b->rectangle.y;
 869                         break;
 870                 case DIR_WEST:
 871                         return (b->rectangle.x + b->rectangle.width) == a->rectangle.x;
 872                         break;
 873                 case DIR_NORTH:
 874                         return (b->rectangle.y + b->rectangle.height) == a->rectangle.y;
 875                         break;
 876         }
 877         return false;
 878 }
 879
 880 node_t *find_fence(node_t *n, direction_t dir)
 881 {
 882         node_t *p;
 883
 884         if (n == NULL) {
 885                 return NULL;
 886         }
 887
 888         p = n->parent;
 889
 890         while (p != NULL) {
 891                 if ((dir == DIR_NORTH && p->split_type == TYPE_HORIZONTAL && p->rectangle.y < n->rectangle.y) ||
 892                     (dir == DIR_WEST && p->split_type == TYPE_VERTICAL && p->rectangle.x < n->rectangle.x) ||
 893                     (dir == DIR_SOUTH && p->split_type == TYPE_HORIZONTAL && (p->rectangle.y + p->rectangle.height) > (n->rectangle.y + n->rectangle.height)) ||
 894                     (dir == DIR_EAST && p->split_type == TYPE_VERTICAL && (p->rectangle.x + p->rectangle.width) > (n->rectangle.x + n->rectangle.width)))
 895                         return p;
 896                 p = p->parent;
 897         }
 898
 899         return NULL;
 900 }
 901
 902 /* returns *true* if *a* is a child of *b* */
 903 bool is_child(node_t *a, node_t *b)
 904 {
 905         if (a == NULL || b == NULL) {
 906                 return false;
 907         }
 908         return (a->parent != NULL && a->parent == b);
 909 }
 910
 911 /* returns *true* if *a* is a descendant of *b* */
 912 bool is_descendant(node_t *a, node_t *b)
 913 {
 914         if (a == NULL || b == NULL) {
 915                 return false;
 916         }
 917         while (a != b && a != NULL) {
 918                 a = a->parent;
 919         }
 920         return a == b;
 921 }
 922
 923 bool find_by_id(uint32_t id, coordinates_t *loc)
 924 {
 925         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
 926                 for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
 927                         node_t *n = find_by_id_in(d->root, id);
 928                         if (n != NULL) {
 929                                 loc->monitor = m;
 930                                 loc->desktop = d;
 931                                 loc->node = n;
 932                                 return true;
 933                         }
 934                 }
 935         }
 936         return false;
 937 }
 938
 939 node_t *find_by_id_in(node_t *r, uint32_t id)
 940 {
 941         if (r == NULL) {
 942                 return NULL;
 943         } else if (r->id == id) {
 944                 return r;
 945         } else {
 946                 node_t *f = find_by_id_in(r->first_child, id);
 947                 if (f != NULL) {
 948                         return f;
 949                 } else {
 950                         return find_by_id_in(r->second_child, id);
 951                 }
 952         }
 953 }
 954
 955 /* Based on https://github.com/ntrrgc/right-window */
 956 void find_nearest_neighbor(coordinates_t *ref, coordinates_t *dst, direction_t dir, node_select_t sel)
 957 {
 958         xcb_rectangle_t rect = get_rectangle(ref->monitor, ref->desktop, ref->node);
 959         double md = UINT32_MAX, mr = UINT32_MAX;
 960
 961         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
 962                 desktop_t *d = m->desk;
 963                 for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
 964                         coordinates_t loc = {m, d, f};
 965                         xcb_rectangle_t r = get_rectangle(m, d, f);
 966                         if (f == ref->node ||
 967                             f->client == NULL ||
 968                             f->hidden ||
 969                             is_descendant(f, ref->node) ||
 970                             !node_matches(&loc, ref, sel) ||
 971                             !on_dir_side(rect, r, dir)) {
 972                                 continue;
 973                         }
 974                         uint32_t fd = boundary_distance(rect, r, dir);
 975                         uint32_t fr = history_rank(f);
 976                         if (fd < md || (fd == md && fr < mr)) {
 977                                 md = fd;
 978                                 mr = fr;
 979                                 *dst = loc;
 980                         }
 981                 }
 982         }
 983 }
 984
 985 unsigned int node_area(desktop_t *d, node_t *n)
 986 {
 987         if (n == NULL) {
 988                 return 0;
 989         }
 990         return area(get_rectangle(NULL, d, n));
 991 }
 992
 993 int tiled_count(node_t *n)
 994 {
 995         if (n == NULL) {
 996                 return 0;
 997         }
 998         int cnt = 0;
 999         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1000                 if (!f->hidden && f->client != NULL && IS_TILED(f->client)) {
1001                         cnt++;
1002                 }
1003         }
1004         return cnt;
1005 }
1006
1007 void find_biggest(coordinates_t *ref, coordinates_t *dst, node_select_t sel)
1008 {
1009         unsigned int b_area = 0;
1010
1011         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
1012                 for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
1013                         for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
1014                                 coordinates_t loc = {m, d, f};
1015                                 if (f->client == NULL || f->vacant || !node_matches(&loc, ref, sel)) {
1016                                         continue;
1017                                 }
1018                                 unsigned int f_area = node_area(d, f);
1019                                 if (f_area > b_area) {
1020                                         *dst = loc;
1021                                         b_area = f_area;
1022                                 }
1023                         }
1024                 }
1025         }
1026 }
1027
1028 void rotate_tree(node_t *n, int deg)
1029 {
1030         rotate_tree_rec(n, deg);
1031         rebuild_constraints(n);
1032 }
1033
1034 void rotate_tree_rec(node_t *n, int deg)
1035 {
1036         if (n == NULL || is_leaf(n) || deg == 0) {
1037                 return;
1038         }
1039
1040         node_t *tmp;
1041
1042         if ((deg == 90 && n->split_type == TYPE_HORIZONTAL) ||
1043             (deg == 270 && n->split_type == TYPE_VERTICAL) ||
1044             deg == 180) {
1045                 tmp = n->first_child;
1046                 n->first_child = n->second_child;
1047                 n->second_child = tmp;
1048                 n->split_ratio = 1.0 - n->split_ratio;
1049         }
1050
1051         if (deg != 180) {
1052                 if (n->split_type == TYPE_HORIZONTAL) {
1053                         n->split_type = TYPE_VERTICAL;
1054                 } else if (n->split_type == TYPE_VERTICAL) {
1055                         n->split_type = TYPE_HORIZONTAL;
1056                 }
1057         }
1058
1059         rotate_tree_rec(n->first_child, deg);
1060         rotate_tree_rec(n->second_child, deg);
1061 }
1062
1063 void rotate_brother(node_t *n)
1064 {
1065         rotate_tree(brother_tree(n), n->birth_rotation);
1066 }
1067
1068 void unrotate_tree(node_t *n, int rot)
1069 {
1070         if (rot == 0) {
1071                 return;
1072         }
1073         rotate_tree(n, 360 - rot);
1074 }
1075
1076 void unrotate_brother(node_t *n)
1077 {
1078         unrotate_tree(brother_tree(n), n->birth_rotation);
1079 }
1080
1081 void flip_tree(node_t *n, flip_t flp)
1082 {
1083         if (n == NULL || is_leaf(n)) {
1084                 return;
1085         }
1086
1087         node_t *tmp;
1088
1089         if ((flp == FLIP_HORIZONTAL && n->split_type == TYPE_HORIZONTAL) ||
1090             (flp == FLIP_VERTICAL && n->split_type == TYPE_VERTICAL)) {
1091                 tmp = n->first_child;
1092                 n->first_child = n->second_child;
1093                 n->second_child = tmp;
1094                 n->split_ratio = 1.0 - n->split_ratio;
1095         }
1096
1097         flip_tree(n->first_child, flp);
1098         flip_tree(n->second_child, flp);
1099 }
1100
1101 void equalize_tree(node_t *n)
1102 {
1103         if (n == NULL || n->vacant) {
1104                 return;
1105         } else {
1106                 n->split_ratio = split_ratio;
1107                 equalize_tree(n->first_child);
1108                 equalize_tree(n->second_child);
1109         }
1110 }
1111
1112 int balance_tree(node_t *n)
1113 {
1114         if (n == NULL || n->vacant) {
1115                 return 0;
1116         } else if (is_leaf(n)) {
1117                 return 1;
1118         } else {
1119                 int b1 = balance_tree(n->first_child);
1120                 int b2 = balance_tree(n->second_child);
1121                 int b = b1 + b2;
1122                 if (b1 > 0 && b2 > 0) {
1123                         n->split_ratio = (double) b1 / b;
1124                 }
1125                 return b;
1126         }
1127 }
1128
1129 void unlink_node(monitor_t *m, desktop_t *d, node_t *n)
1130 {
1131         if (d == NULL || n == NULL) {
1132                 return;
1133         }
1134
1135         node_t *p = n->parent;
1136
1137         if (p == NULL) {
1138                 d->root = NULL;
1139                 d->focus = NULL;
1140         } else {
1141                 if (d->focus == p || is_descendant(d->focus, n)) {
1142                         d->focus = NULL;
1143                 }
1144
1145                 history_remove(d, p, false);
1146                 cancel_presel(m, d, p);
1147                 if (p->sticky) {
1148                         m->sticky_count--;
1149                 }
1150
1151                 node_t *b = brother_tree(n);
1152                 node_t *g = p->parent;
1153
1154                 if (!n->vacant) {
1155                         unrotate_tree(b, n->birth_rotation);
1156                 }
1157
1158                 b->parent = g;
1159
1160                 if (g != NULL) {
1161                         if (is_first_child(p)) {
1162                                 g->first_child = b;
1163                         } else {
1164                                 g->second_child = b;
1165                         }
1166                 } else {
1167                         d->root = b;
1168                 }
1169
1170                 b->birth_rotation = p->birth_rotation;
1171
1172                 free(p);
1173                 n->parent = NULL;
1174
1175                 propagate_flags_upward(m, d, b);
1176         }
1177 }
1178
1179 void close_node(node_t *n)
1180 {
1181         if (n == NULL) {
1182                 return;
1183         } else if (n->client != NULL) {
1184                 if (n->client->icccm_props.delete_window) {
1185                         send_client_message(n->id, ewmh->WM_PROTOCOLS, WM_DELETE_WINDOW);
1186                 } else {
1187                         xcb_kill_client(dpy, n->id);
1188                 }
1189         } else {
1190                 close_node(n->first_child);
1191                 close_node(n->second_child);
1192         }
1193 }
1194
1195 void kill_node(monitor_t *m, desktop_t *d, node_t *n)
1196 {
1197         if (n == NULL) {
1198                 return;
1199         }
1200
1201         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1202                 if (f->client != NULL) {
1203                         xcb_kill_client(dpy, f->id);
1204                 }
1205         }
1206
1207         remove_node(m, d, n);
1208 }
1209
1210 void remove_node(monitor_t *m, desktop_t *d, node_t *n)
1211 {
1212         if (n == NULL) {
1213                 return;
1214         }
1215
1216         unlink_node(m, d, n);
1217         history_remove(d, n, true);
1218         remove_stack_node(n);
1219         cancel_presel_in(m, d, n);
1220         if (m->sticky_count > 0) {
1221                 m->sticky_count -= sticky_count(n);
1222         }
1223         clients_count -= clients_count_in(n);
1224         if (is_descendant(grabbed_node, n)) {
1225                 grabbed_node = NULL;
1226         }
1227         free_node(n);
1228
1229         ewmh_update_client_list(false);
1230         ewmh_update_client_list(true);
1231
1232         if (mon != NULL && d->focus == NULL) {
1233                 if (d == mon->desk) {
1234                         focus_node(m, d, NULL);
1235                 } else {
1236                         activate_node(m, d, NULL);
1237                 }
1238         }
1239 }
1240
1241 void free_node(node_t *n)
1242 {
1243         if (n == NULL) {
1244                 return;
1245         }
1246         node_t *first_child = n->first_child;
1247         node_t *second_child = n->second_child;
1248         free(n->client);
1249         free(n);
1250         free_node(first_child);
1251         free_node(second_child);
1252 }
1253
1254 bool swap_nodes(monitor_t *m1, desktop_t *d1, node_t *n1, monitor_t *m2, desktop_t *d2, node_t *n2)
1255 {
1256         if (n1 == NULL || n2 == NULL || n1 == n2 || is_descendant(n1, n2) || is_descendant(n2, n1) ||
1257             (d1 != d2 && ((m1->sticky_count > 0 && sticky_count(n1) > 0) ||
1258                           (m2->sticky_count > 0 && sticky_count(n2) > 0)))) {
1259                 return false;
1260         }
1261
1262         put_status(SBSC_MASK_NODE_SWAP, "node_swap 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X\n", m1->id, d1->id, n1->id, m2->id, d2->id, n2->id);
1263
1264         node_t *pn1 = n1->parent;
1265         node_t *pn2 = n2->parent;
1266         bool n1_first_child = is_first_child(n1);
1267         bool n2_first_child = is_first_child(n2);
1268         int br1 = n1->birth_rotation;
1269         int br2 = n2->birth_rotation;
1270         bool n1_held_focus = is_descendant(d1->focus, n1);
1271         bool n2_held_focus = is_descendant(d2->focus, n2);
1272         node_t *last_d1_focus = d1->focus;
1273         node_t *last_d2_focus = d2->focus;
1274
1275         if (pn1 != NULL) {
1276                 if (n1_first_child) {
1277                         pn1->first_child = n2;
1278                 } else {
1279                         pn1->second_child = n2;
1280                 }
1281         }
1282
1283         if (pn2 != NULL) {
1284                 if (n2_first_child) {
1285                         pn2->first_child = n1;
1286                 } else {
1287                         pn2->second_child = n1;
1288                 }
1289         }
1290
1291         n1->parent = pn2;
1292         n2->parent = pn1;
1293         n1->birth_rotation = br2;
1294         n2->birth_rotation = br1;
1295
1296         propagate_flags_upward(m2, d2, n1);
1297         propagate_flags_upward(m1, d1, n2);
1298
1299         if (d1 != d2) {
1300                 if (d1->root == n1) {
1301                         d1->root = n2;
1302                 }
1303
1304                 if (d2->root == n2) {
1305                         d2->root = n1;
1306                 }
1307
1308                 if (n1_held_focus) {
1309                         d1->focus = n2_held_focus ? last_d2_focus : n2;
1310                 }
1311
1312                 if (n2_held_focus) {
1313                         d2->focus = n1_held_focus ? last_d1_focus : n1;
1314                 }
1315
1316                 if (m1 != m2) {
1317                         adapt_geometry(&m2->rectangle, &m1->rectangle, n2);
1318                         adapt_geometry(&m1->rectangle, &m2->rectangle, n1);
1319                 }
1320
1321                 ewmh_set_wm_desktop(n1, d2);
1322                 ewmh_set_wm_desktop(n2, d1);
1323
1324                 history_swap_nodes(m1, d1, n1, m2, d2, n2);
1325
1326                 if (m1->desk != d1 && m2->desk == d2) {
1327                         show_node(d2, n1);
1328                         hide_node(d2, n2);
1329                 } else if (m1->desk == d1 && m2->desk != d2) {
1330                         hide_node(d1, n1);
1331                         show_node(d1, n2);
1332                 }
1333
1334                 bool d1_was_focused = (d1 == mon->desk);
1335                 bool d2_was_focused = (d2 == mon->desk);
1336
1337                 if (n1_held_focus) {
1338                         if (d1_was_focused) {
1339                                 focus_node(m2, d2, last_d1_focus);
1340                         } else {
1341                                 activate_node(m1, d1, d1->focus);
1342                         }
1343                 } else {
1344                         draw_border(n2, is_descendant(n2, d1->focus), (m1 == mon));
1345                 }
1346
1347                 if (n2_held_focus) {
1348                         if (d2_was_focused) {
1349                                 focus_node(m1, d1, last_d2_focus);
1350                         } else {
1351                                 activate_node(m2, d2, d2->focus);
1352                         }
1353                 } else {
1354                         draw_border(n1, is_descendant(n1, d2->focus), (m2 == mon));
1355                 }
1356         } else {
1357                 draw_border(n1, is_descendant(n1, d2->focus), (m2 == mon));
1358                 draw_border(n2, is_descendant(n2, d1->focus), (m1 == mon));
1359         }
1360
1361         arrange(m1, d1);
1362
1363         if (d1 != d2) {
1364                 arrange(m2, d2);
1365         }
1366
1367         return true;
1368 }
1369
1370 bool transfer_node(monitor_t *ms, desktop_t *ds, node_t *ns, monitor_t *md, desktop_t *dd, node_t *nd)
1371 {
1372         if (ns == NULL || ns == nd || is_child(ns, nd) || is_descendant(nd, ns)) {
1373                 return false;
1374         }
1375
1376         if (sticky_still && ds != dd && ms->sticky_count > 0 && sticky_count(ns) > 0) {
1377                 return false;
1378         }
1379
1380         put_status(SBSC_MASK_NODE_TRANSFER, "node_transfer 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X\n", ms->id, ds->id, ns->id, md->id, dd->id, nd!=NULL?nd->id:0);
1381
1382         bool held_focus = is_descendant(ds->focus, ns);
1383         /* avoid ending up with a dangling pointer (because of unlink_node) */
1384         node_t *last_ds_focus = is_child(ns, ds->focus) ? NULL : ds->focus;
1385
1386         if (held_focus && ds == mon->desk) {
1387                 clear_input_focus();
1388         }
1389
1390         unlink_node(ms, ds, ns);
1391         insert_node(md, dd, ns, nd);
1392
1393         if (md != ms && (ns->client == NULL || monitor_from_client(ns->client) != md)) {
1394                 adapt_geometry(&ms->rectangle, &md->rectangle, ns);
1395         }
1396
1397         if (ds != dd) {
1398                 ewmh_set_wm_desktop(ns, dd);
1399                 if (sticky_still) {
1400                         if (ds == ms->desk && dd != md->desk) {
1401                                 hide_node(ds, ns);
1402                         } else if (ds != ms->desk && dd == md->desk) {
1403                                 show_node(dd, ns);
1404                         }
1405                 }
1406         }
1407
1408         history_transfer_node(md, dd, ns);
1409         stack(dd, ns, false);
1410
1411         if (ds == dd) {
1412                 if (held_focus) {
1413                         if (ds == mon->desk) {
1414                                 focus_node(ms, ds, last_ds_focus);
1415                         } else {
1416                                 activate_node(ms, ds, last_ds_focus);
1417                         }
1418                 } else {
1419                         draw_border(ns, is_descendant(ns, ds->focus), (ms == mon));
1420                 }
1421         } else {
1422                 if (held_focus) {
1423                         if (ds == mon->desk) {
1424                                 focus_node(md, dd, last_ds_focus);
1425                         }
1426                         activate_node(ms, ds, ds->focus);
1427                 }
1428                 if (dd->focus == ns) {
1429                         if (dd == mon->desk) {
1430                                 focus_node(md, dd, held_focus ? last_ds_focus : ns);
1431                         } else {
1432                                 activate_node(md, dd, held_focus ? last_ds_focus : ns);
1433                         }
1434                 } else {
1435                         draw_border(ns, is_descendant(ns, dd->focus), (md == mon));
1436                 }
1437         }
1438
1439         arrange(ms, ds);
1440
1441         if (ds != dd) {
1442                 arrange(md, dd);
1443         }
1444
1445         return true;
1446 }
1447
1448 bool find_closest_node(coordinates_t *ref, coordinates_t *dst, cycle_dir_t dir, node_select_t sel)
1449 {
1450         monitor_t *m = ref->monitor;
1451         desktop_t *d = ref->desktop;
1452         node_t *n = ref->node;
1453         n = (dir == CYCLE_PREV ? prev_leaf(n, d->root) : next_leaf(n, d->root));
1454
1455 #define HANDLE_BOUNDARIES(m, d, n)  \
1456         while (n == NULL) { \
1457                 d = (dir == CYCLE_PREV ? d->prev : d->next); \
1458                 if (d == NULL) { \
1459                         m = (dir == CYCLE_PREV ? m->prev : m->next); \
1460                         if (m == NULL) { \
1461                                 m = (dir == CYCLE_PREV ? mon_tail : mon_head); \
1462                         } \
1463                         d = (dir == CYCLE_PREV ? m->desk_tail : m->desk_head); \
1464                 } \
1465                 n = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root)); \
1466                 if (ref->node == NULL && d == ref->desktop) { \
1467                         break; \
1468                 } \
1469         }
1470         HANDLE_BOUNDARIES(m, d, n);
1471
1472         while (n != ref->node) {
1473                 coordinates_t loc = {m, d, n};
1474                 if (n->client != NULL && !n->hidden && node_matches(&loc, ref, sel)) {
1475                         *dst = loc;
1476                         return true;
1477                 }
1478                 n = (dir == CYCLE_PREV ? prev_leaf(n, d->root) : next_leaf(n, d->root));
1479                 HANDLE_BOUNDARIES(m, d, n);
1480         }
1481 #undef HANDLE_BOUNDARIES
1482         return false;
1483 }
1484
1485 void circulate_leaves(monitor_t *m, desktop_t *d, node_t *n, circulate_dir_t dir)
1486 {
1487         if (tiled_count(n) < 2) {
1488                 return;
1489         }
1490         node_t *p = d->focus->parent;
1491         bool focus_first_child = is_first_child(d->focus);
1492         if (dir == CIRCULATE_FORWARD) {
1493                 node_t *e = second_extrema(n);
1494                 while (e != NULL && (e->client == NULL || !IS_TILED(e->client))) {
1495                         e = prev_leaf(e, n);
1496                 }
1497                 for (node_t *s = e, *f = prev_tiled_leaf(s, n); f != NULL; s = prev_tiled_leaf(f, n), f = prev_tiled_leaf(s, n)) {
1498                         swap_nodes(m, d, f, m, d, s);
1499                 }
1500         } else {
1501                 node_t *e = first_extrema(n);
1502                 while (e != NULL && (e->client == NULL || !IS_TILED(e->client))) {
1503                         e = next_leaf(e, n);
1504                 }
1505                 for (node_t *f = e, *s = next_tiled_leaf(f, n); s != NULL; f = next_tiled_leaf(s, n), s = next_tiled_leaf(f, n)) {
1506                         swap_nodes(m, d, f, m, d, s);
1507                 }
1508         }
1509         if (p != NULL) {
1510                 node_t *f = focus_first_child ? p->first_child : p->second_child;
1511                 if (is_leaf(f)) {
1512                         if (d == mon->desk) {
1513                                 focus_node(m, d, f);
1514                         } else {
1515                                 activate_node(m, d, f);
1516                         }
1517                 }
1518         }
1519 }
1520
1521 void set_vacant(monitor_t *m, desktop_t *d, node_t *n, bool value)
1522 {
1523         if (n->vacant == value) {
1524                 return;
1525         }
1526
1527         propagate_vacant_downward(m, d, n, value);
1528         propagate_vacant_upward(m, d, n);
1529 }
1530
1531 void set_vacant_local(monitor_t *m, desktop_t *d, node_t *n, bool value)
1532 {
1533         if (n->vacant == value) {
1534                 return;
1535         }
1536
1537         n->vacant = value;
1538
1539         if (value) {
1540                 unrotate_brother(n);
1541                 cancel_presel(m, d, n);
1542         } else {
1543                 rotate_brother(n);
1544         }
1545 }
1546
1547 void propagate_vacant_downward(monitor_t *m, desktop_t *d, node_t *n, bool value)
1548 {
1549         if (n == NULL) {
1550                 return;
1551         }
1552
1553         set_vacant_local(m, d, n, value);
1554
1555         propagate_vacant_downward(m, d, n->first_child, value);
1556         propagate_vacant_downward(m, d, n->second_child, value);
1557 }
1558
1559 void propagate_vacant_upward(monitor_t *m, desktop_t *d, node_t *n)
1560 {
1561         if (n == NULL) {
1562                 return;
1563         }
1564
1565         node_t *p = n->parent;
1566
1567         if (p != NULL) {
1568                 set_vacant_local(m, d, p, (p->first_child->vacant && p->second_child->vacant));
1569         }
1570
1571         propagate_vacant_upward(m, d, p);
1572 }
1573
1574 bool set_layer(monitor_t *m, desktop_t *d, node_t *n, stack_layer_t l)
1575 {
1576         if (n == NULL || n->client == NULL || n->client->layer == l) {
1577                 return false;
1578         }
1579
1580         n->client->last_layer = n->client->layer;
1581         n->client->layer = l;
1582
1583         if (l == LAYER_ABOVE) {
1584                 n->client->wm_flags |= WM_FLAG_ABOVE;
1585                 n->client->wm_flags &= ~WM_FLAG_BELOW;
1586         } else if (l == LAYER_BELOW) {
1587                 n->client->wm_flags |= WM_FLAG_BELOW;
1588                 n->client->wm_flags &= ~WM_FLAG_ABOVE;
1589         } else {
1590                 n->client->wm_flags &= ~(WM_FLAG_ABOVE | WM_FLAG_BELOW);
1591         }
1592
1593         ewmh_wm_state_update(n);
1594
1595         put_status(SBSC_MASK_NODE_LAYER, "node_layer 0x%08X 0x%08X 0x%08X %s\n", m->id, d->id, n->id, LAYER_STR(l));
1596
1597         if (d->focus == n) {
1598                 neutralize_occluding_windows(m, d, n);
1599         }
1600
1601         stack(d, n, (d->focus == n));
1602
1603         return true;
1604 }
1605
1606 bool set_state(monitor_t *m, desktop_t *d, node_t *n, client_state_t s)
1607 {
1608         if (n == NULL || n->client == NULL || n->client->state == s) {
1609                 return false;
1610         }
1611
1612         client_t *c = n->client;
1613
1614         c->last_state = c->state;
1615         c->state = s;
1616
1617         switch (c->last_state) {
1618                 case STATE_TILED:
1619                 case STATE_PSEUDO_TILED:
1620                         break;
1621                 case STATE_FLOATING:
1622                         set_floating(m, d, n, false);
1623                         break;
1624                 case STATE_FULLSCREEN:
1625                         set_fullscreen(m, d, n, false);
1626                         break;
1627         }
1628
1629         put_status(SBSC_MASK_NODE_STATE, "node_state 0x%08X 0x%08X 0x%08X %s off\n", m->id, d->id, n->id, STATE_STR(c->last_state));
1630
1631         switch (c->state) {
1632                 case STATE_TILED:
1633                 case STATE_PSEUDO_TILED:
1634                         break;
1635                 case STATE_FLOATING:
1636                         set_floating(m, d, n, true);
1637                         break;
1638                 case STATE_FULLSCREEN:
1639                         set_fullscreen(m, d, n, true);
1640                         break;
1641         }
1642
1643         put_status(SBSC_MASK_NODE_STATE, "node_state 0x%08X 0x%08X 0x%08X %s on\n", m->id, d->id, n->id, STATE_STR(c->state));
1644
1645         if (n == m->desk->focus) {
1646                 put_status(SBSC_MASK_REPORT);
1647         }
1648
1649         return true;
1650 }
1651
1652 void set_floating(monitor_t *m, desktop_t *d, node_t *n, bool value)
1653 {
1654         if (n == NULL) {
1655                 return;
1656         }
1657
1658         cancel_presel(m, d, n);
1659         set_vacant(m, d, n, value);
1660
1661         if (!value && d->focus == n) {
1662                 neutralize_occluding_windows(m, d, n);
1663         }
1664
1665         stack(d, n, (d->focus == n));
1666 }
1667
1668 void set_fullscreen(monitor_t *m, desktop_t *d, node_t *n, bool value)
1669 {
1670         if (n == NULL) {
1671                 return;
1672         }
1673
1674         client_t *c = n->client;
1675
1676         cancel_presel(m, d, n);
1677         set_vacant(m, d, n, value);
1678
1679         if (value) {
1680                 c->wm_flags |= WM_FLAG_FULLSCREEN;
1681                 c->last_layer = c->layer;
1682                 c->layer = LAYER_ABOVE;
1683         } else {
1684                 c->wm_flags &= ~WM_FLAG_FULLSCREEN;
1685                 c->layer = c->last_layer;
1686                 if (d->focus == n) {
1687                         neutralize_occluding_windows(m, d, n);
1688                 }
1689         }
1690
1691         ewmh_wm_state_update(n);
1692         stack(d, n, (d->focus == n));
1693 }
1694
1695 void neutralize_occluding_windows(monitor_t *m, desktop_t *d, node_t *n)
1696 {
1697         bool changed = false;
1698         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1699                 for (node_t *a = first_extrema(d->root); a != NULL; a = next_leaf(a, d->root)) {
1700                         if (a != f && a->client != NULL && f->client != NULL &&
1701                             IS_FULLSCREEN(a->client) && stack_cmp(f->client, a->client) < 0) {
1702                                 set_state(m, d, a, a->client->last_state);
1703                                 changed = true;
1704                         }
1705                 }
1706         }
1707         if (changed) {
1708                 arrange(m, d);
1709         }
1710 }
1711
1712 void rebuild_constraints(node_t *n)
1713 {
1714         if (n == NULL || is_leaf(n)) {
1715                 return;
1716         } else {
1717                 rebuild_constraints(n->first_child);
1718                 rebuild_constraints(n->second_child);
1719                 update_constraints(n);
1720         }
1721 }
1722
1723 void update_constraints(node_t *n)
1724 {
1725         if (n == NULL || is_leaf(n)) {
1726                 return;
1727         }
1728         if (n->split_type == TYPE_VERTICAL) {
1729                 n->constraints.min_width = n->first_child->constraints.min_width + n->second_child->constraints.min_width;
1730                 n->constraints.min_height = MAX(n->first_child->constraints.min_height, n->second_child->constraints.min_height);
1731         } else {
1732                 n->constraints.min_width = MAX(n->first_child->constraints.min_width, n->second_child->constraints.min_width);
1733                 n->constraints.min_height = n->first_child->constraints.min_height + n->second_child->constraints.min_height;
1734         }
1735 }
1736
1737 void propagate_flags_upward(monitor_t *m, desktop_t *d, node_t *n)
1738 {
1739         if (n == NULL) {
1740                 return;
1741         }
1742
1743         node_t *p = n->parent;
1744
1745         if (p != NULL) {
1746                 set_vacant_local(m, d, p, (p->first_child->vacant && p->second_child->vacant));
1747                 set_hidden_local(m, d, p, (p->first_child->hidden && p->second_child->hidden));
1748                 update_constraints(p);
1749         }
1750
1751         propagate_flags_upward(m, d, p);
1752 }
1753
1754 void set_hidden(monitor_t *m, desktop_t *d, node_t *n, bool value)
1755 {
1756         if (n == NULL || n->hidden == value) {
1757                 return;
1758         }
1759
1760         bool held_focus = is_descendant(d->focus, n);
1761
1762         propagate_hidden_downward(m, d, n, value);
1763         propagate_hidden_upward(m, d, n);
1764
1765         put_status(SBSC_MASK_NODE_FLAG, "node_flag 0x%08X 0x%08X 0x%08X hidden %s\n", m->id, d->id, n->id, ON_OFF_STR(value));
1766
1767         if (held_focus || d->focus == NULL) {
1768                 if (d->focus != NULL) {
1769                         d->focus = NULL;
1770                         draw_border(n, false, (mon == m));
1771                 }
1772                 if (d == mon->desk) {
1773                         focus_node(m, d, d->focus);
1774                 } else {
1775                         activate_node(m, d, d->focus);
1776                 }
1777         }
1778 }
1779
1780 void set_hidden_local(monitor_t *m, desktop_t *d, node_t *n, bool value)
1781 {
1782         if (n->hidden == value) {
1783                 return;
1784         }
1785
1786         n->hidden = value;
1787
1788         if (n->client != NULL) {
1789                 if (n->client->shown) {
1790                         window_set_visibility(n->id, !value);
1791                 }
1792
1793                 if (IS_TILED(n->client)) {
1794                         set_vacant(m, d, n, value);
1795                 }
1796
1797                 if (value) {
1798                         n->client->wm_flags |= WM_FLAG_HIDDEN;
1799                 } else {
1800                         n->client->wm_flags &= ~WM_FLAG_HIDDEN;
1801                 }
1802
1803                 ewmh_wm_state_update(n);
1804         }
1805 }
1806
1807 void propagate_hidden_downward(monitor_t *m, desktop_t *d, node_t *n, bool value)
1808 {
1809         if (n == NULL) {
1810                 return;
1811         }
1812
1813         set_hidden_local(m, d, n, value);
1814
1815         propagate_hidden_downward(m, d, n->first_child, value);
1816         propagate_hidden_downward(m, d, n->second_child, value);
1817 }
1818
1819 void propagate_hidden_upward(monitor_t *m, desktop_t *d, node_t *n)
1820 {
1821         if (n == NULL) {
1822                 return;
1823         }
1824
1825         node_t *p = n->parent;
1826
1827         if (p != NULL) {
1828                 set_hidden_local(m, d, p, p->first_child->hidden && p->second_child->hidden);
1829         }
1830
1831         propagate_hidden_upward(m, d, p);
1832 }
1833
1834 void set_sticky(monitor_t *m, desktop_t *d, node_t *n, bool value)
1835 {
1836         if (n == NULL || n->sticky == value) {
1837                 return;
1838         }
1839
1840         if (d != m->desk) {
1841                 transfer_node(m, d, n, m, m->desk, m->desk->focus);
1842         }
1843
1844         n->sticky = value;
1845
1846         if (value) {
1847                 m->sticky_count++;
1848         } else {
1849                 m->sticky_count--;
1850         }
1851
1852         if (n->client != NULL) {
1853                 if (value) {
1854                         n->client->wm_flags |= WM_FLAG_STICKY;
1855                 } else {
1856                         n->client->wm_flags &= ~WM_FLAG_STICKY;
1857                 }
1858                 ewmh_wm_state_update(n);
1859         }
1860
1861         put_status(SBSC_MASK_NODE_FLAG, "node_flag 0x%08X 0x%08X 0x%08X sticky %s\n", m->id, d->id, n->id, ON_OFF_STR(value));
1862
1863         if (n == m->desk->focus) {
1864                 put_status(SBSC_MASK_REPORT);
1865         }
1866 }
1867
1868 void set_private(monitor_t *m, desktop_t *d, node_t *n, bool value)
1869 {
1870         if (n == NULL || n->private == value) {
1871                 return;
1872         }
1873
1874         n->private = value;
1875
1876         put_status(SBSC_MASK_NODE_FLAG, "node_flag 0x%08X 0x%08X 0x%08X private %s\n", m->id, d->id, n->id, ON_OFF_STR(value));
1877
1878         if (n == m->desk->focus) {
1879                 put_status(SBSC_MASK_REPORT);
1880         }
1881 }
1882
1883 void set_locked(monitor_t *m, desktop_t *d, node_t *n, bool value)
1884 {
1885         if (n == NULL || n->locked == value) {
1886                 return;
1887         }
1888
1889         n->locked = value;
1890
1891         put_status(SBSC_MASK_NODE_FLAG, "node_flag 0x%08X 0x%08X 0x%08X locked %s\n", m->id, d->id, n->id, ON_OFF_STR(value));
1892
1893         if (n == m->desk->focus) {
1894                 put_status(SBSC_MASK_REPORT);
1895         }
1896 }
1897
1898 void set_urgent(monitor_t *m, desktop_t *d, node_t *n, bool value)
1899 {
1900         if (value && mon->desk->focus == n) {
1901                 return;
1902         }
1903
1904         n->client->urgent = value;
1905
1906         if (value) {
1907                 n->client->wm_flags |= WM_FLAG_DEMANDS_ATTENTION;
1908         } else {
1909                 n->client->wm_flags &= ~WM_FLAG_DEMANDS_ATTENTION;
1910         }
1911
1912         ewmh_wm_state_update(n);
1913
1914         put_status(SBSC_MASK_NODE_FLAG, "node_flag 0x%08X 0x%08X 0x%08X urgent %s\n", m->id, d->id, n->id, ON_OFF_STR(value));
1915         put_status(SBSC_MASK_REPORT);
1916 }
1917
1918 /* Returns true if a contains b */
1919 bool contains(xcb_rectangle_t a, xcb_rectangle_t b)
1920 {
1921         return (a.x <= b.x && (a.x + a.width) >= (b.x + b.width) &&
1922                 a.y <= b.y && (a.y + a.height) >= (b.y + b.height));
1923 }
1924
1925 xcb_rectangle_t get_rectangle(monitor_t *m, desktop_t *d, node_t *n)
1926 {
1927         if (n == NULL) {
1928                 return m->rectangle;
1929         }
1930         client_t *c = n->client;
1931         if (c != NULL) {
1932                 if (IS_FLOATING(c)) {
1933                         return c->floating_rectangle;
1934                 } else {
1935                         return c->tiled_rectangle;
1936                 }
1937         } else {
1938                 int wg = (d == NULL ? 0 : (gapless_monocle && IS_MONOCLE(d) ? 0 : d->window_gap));
1939                 xcb_rectangle_t rect = n->rectangle;
1940                 rect.width -= wg;
1941                 rect.height -= wg;
1942                 return rect;
1943         }
1944 }
1945
1946 void listen_enter_notify(node_t *n, bool enable)
1947 {
1948         uint32_t mask = CLIENT_EVENT_MASK | (enable ? XCB_EVENT_MASK_ENTER_WINDOW : 0);
1949         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1950                 if (f->client == NULL) {
1951                         continue;
1952                 }
1953                 xcb_change_window_attributes(dpy, f->id, XCB_CW_EVENT_MASK, &mask);
1954                 if (f->presel != NULL) {
1955                         xcb_change_window_attributes(dpy, f->presel->feedback, XCB_CW_EVENT_MASK, &mask);
1956                 }
1957         }
1958 }
1959
1960 void regenerate_ids_in(node_t *n)
1961 {
1962         if (n == NULL || n->client != NULL) {
1963                 return;
1964         }
1965         n->id = xcb_generate_id(dpy);
1966         regenerate_ids_in(n->first_child);
1967         regenerate_ids_in(n->second_child);
1968 }
1969
1970 #define DEF_FLAG_COUNT(flag) \
1971         unsigned int flag##_count(node_t *n) \
1972         { \
1973                 if (n == NULL) { \
1974                         return 0; \
1975                 } else { \
1976                         return ((n->flag ? 1 : 0) + \
1977                                 flag##_count(n->first_child) + \
1978                                 flag##_count(n->second_child)); \
1979                 } \
1980         }
1981         DEF_FLAG_COUNT(sticky)
1982         DEF_FLAG_COUNT(private)
1983         DEF_FLAG_COUNT(locked)
1984 #undef DEF_FLAG_COUNT