tree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <ctype.h>
   5 #include <math.h>
   6 #include <float.h>
   7 #include <xcb/xcb.h>
   8 #include <xcb/xcb_event.h>
   9 #include "settings.h"
  10 #include "helpers.h"
  11 #include "window.h"
  12 #include "types.h"
  13 #include "bspwm.h"
  14 #include "ewmh.h"
  15 #include "tree.h"
  16
  17 bool is_leaf(node_t *n)
  18 {
  19     return (n != NULL && n->first_child == NULL && n->second_child == NULL);
  20 }
  21
  22 bool is_tiled(client_t *c)
  23 {
  24     if (c == NULL)
  25         return false;
  26     return (!c->floating && !c->transient && !c->fullscreen);
  27 }
  28
  29 bool is_floating(client_t *c)
  30 {
  31     if (c == NULL)
  32         return false;
  33     return (c->floating && !c->fullscreen);
  34 }
  35
  36 bool is_first_child(node_t *n)
  37 {
  38     return (n != NULL && n->parent != NULL && n->parent->first_child == n);
  39 }
  40
  41 bool is_second_child(node_t *n)
  42 {
  43     return (n != NULL && n->parent != NULL && n->parent->second_child == n);
  44 }
  45
  46 void change_split_ratio(node_t *n, value_change_t chg) {
  47     n->split_ratio = pow(n->split_ratio, (chg == CHANGE_INCREASE ? INC_EXP : DEC_EXP));
  48 }
  49
  50 node_t *first_extrema(node_t *n)
  51 {
  52     if (n == NULL)
  53         return NULL;
  54     else if (n->first_child == NULL)
  55         return n;
  56     else
  57         return first_extrema(n->first_child);
  58 }
  59
  60 node_t *second_extrema(node_t *n)
  61 {
  62     if (n == NULL)
  63         return NULL;
  64     else if (n->second_child == NULL)
  65         return n;
  66     else
  67         return second_extrema(n->second_child);
  68 }
  69
  70 node_t *next_leaf(node_t *n, node_t *r)
  71 {
  72     if (n == NULL)
  73         return NULL;
  74     node_t *p = n;
  75     while (is_second_child(p) && p != r)
  76         p = p->parent;
  77     if (p == r)
  78         return NULL;
  79     return first_extrema(p->parent->second_child);
  80 }
  81
  82 node_t *prev_leaf(node_t *n, node_t *r)
  83 {
  84     if (n == NULL)
  85         return NULL;
  86     node_t *p = n;
  87     while (is_first_child(p) && p != r)
  88         p = p->parent;
  89     if (p == r)
  90         return NULL;
  91     return second_extrema(p->parent->first_child);
  92 }
  93
  94 node_t *find_fence(node_t *n, direction_t dir)
  95 {
  96     node_t *p;
  97
  98     if (n == NULL)
  99         return NULL;
 100
 101     p = n->parent;
 102
 103     while (p != NULL) {
 104         if ((dir == DIR_UP && p->split_type == TYPE_HORIZONTAL && p->rectangle.y < n->rectangle.y)
 105                 || (dir == DIR_LEFT && p->split_type == TYPE_VERTICAL && p->rectangle.x < n->rectangle.x)
 106                 || (dir == DIR_DOWN && p->split_type == TYPE_HORIZONTAL && (p->rectangle.y + p->rectangle.height) > (n->rectangle.y + n->rectangle.height))
 107                 || (dir == DIR_RIGHT && p->split_type == TYPE_VERTICAL && (p->rectangle.x + p->rectangle.width) > (n->rectangle.x + n->rectangle.width)))
 108             return p;
 109         p = p->parent;
 110     }
 111
 112     return NULL;
 113 }
 114
 115 node_t *find_neighbor(node_t *n, direction_t dir)
 116 {
 117     node_t *fence = find_fence(n, dir);
 118
 119     if (fence == NULL)
 120         return NULL;
 121
 122     if (dir == DIR_UP || dir == DIR_LEFT)
 123         return second_extrema(fence->first_child);
 124     else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 125         return first_extrema(fence->second_child);
 126
 127     return NULL;
 128 }
 129
 130 void get_opposite(direction_t dir, direction_t* val)
 131 {
 132     switch (dir) {
 133         case DIR_RIGHT:
 134             *val = DIR_LEFT;
 135             break;
 136         case DIR_DOWN:
 137             *val = DIR_UP;
 138             break;
 139         case DIR_LEFT:
 140             *val = DIR_RIGHT;
 141             break;
 142         case DIR_UP:
 143             *val = DIR_DOWN;
 144             break;
 145     }
 146 }
 147
 148 node_t *nearest_neighbor(desktop_t *d, node_t *n, direction_t dir)
 149 {
 150     node_t *target = NULL;
 151     if (is_tiled(n->client)) {
 152         target = find_fence(n, dir);
 153         if (target == NULL)
 154             return NULL;
 155         if (dir == DIR_UP || dir == DIR_LEFT)
 156             target = target->first_child;
 157         else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 158             target = target->second_child;
 159     } else {
 160         target = d->root;
 161     }
 162     node_t *nearest = NULL;
 163     direction_t dir2;
 164     xcb_point_t pt;
 165     xcb_point_t pt2;
 166     get_side_handle(n->client, dir, &pt);
 167     get_opposite(dir, &dir2);
 168     double ds = DBL_MAX;
 169     for (node_t *a = first_extrema(target); a != NULL; a = next_leaf(a, target)) {
 170         if (is_tiled(a->client) != is_tiled(n->client) || a == n)
 171             continue;
 172         get_side_handle(a->client, dir2, &pt2);
 173         double ds2 = distance(pt, pt2);
 174         PRINTF("distance %X %g\n", a->client->window, ds2);
 175         if (ds2 < ds) {
 176             ds = ds2;
 177             nearest = a;
 178         }
 179     }
 180     return nearest;
 181 }
 182
 183 int tiled_area(node_t *n)
 184 {
 185     if (n == NULL)
 186         return -1;
 187     xcb_rectangle_t rect = n->client->tiled_rectangle;
 188     return rect.width * rect.height;
 189 }
 190
 191 node_t *find_by_area(desktop_t *d, swap_arg_t a)
 192 {
 193     if (d == NULL)
 194         return NULL;
 195
 196     node_t *r = NULL;
 197     int r_area = tiled_area(r);
 198
 199     for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
 200         int f_area = tiled_area(f);
 201         if (r == NULL) {
 202             r = f;
 203             r_area = f_area;
 204         } else if ((a == SWAP_BIGGEST && f_area > r_area)
 205                 || (a == SWAP_SMALLEST && f_area < r_area)) {
 206             r = f;
 207             r_area = f_area;
 208         }
 209     }
 210
 211     return r;
 212 }
 213
 214 void move_fence(node_t *n, direction_t dir, fence_move_t mov)
 215 {
 216     node_t *fence = find_fence(n, dir);
 217
 218     if (fence == NULL)
 219         return;
 220
 221     if ((mov == MOVE_PUSH && (dir == DIR_RIGHT || dir == DIR_DOWN))
 222             || (mov == MOVE_PULL && (dir == DIR_LEFT || dir == DIR_UP)))
 223         change_split_ratio(fence, CHANGE_INCREASE);
 224     else
 225         change_split_ratio(fence, CHANGE_DECREASE);
 226 }
 227
 228 void rotate_tree(node_t *n, rotate_t rot)
 229 {
 230     if (n == NULL || is_leaf(n))
 231         return;
 232
 233     node_t *tmp;
 234
 235     if ((rot == ROTATE_CLOCKWISE && n->split_type == TYPE_HORIZONTAL)
 236             || (rot == ROTATE_COUNTER_CLOCKWISE && n->split_type == TYPE_VERTICAL)
 237             || rot == ROTATE_FULL_CYCLE) {
 238         tmp = n->first_child;
 239         n->first_child = n->second_child;
 240         n->second_child = tmp;
 241         n->split_ratio = 1.0 - n->split_ratio;
 242     }
 243
 244     if (rot != ROTATE_FULL_CYCLE) {
 245         if (n->split_type == TYPE_HORIZONTAL)
 246             n->split_type = TYPE_VERTICAL;
 247         else if (n->split_type == TYPE_VERTICAL)
 248             n->split_type = TYPE_HORIZONTAL;
 249     }
 250
 251     rotate_tree(n->first_child, rot);
 252     rotate_tree(n->second_child, rot);
 253 }
 254
 255 void rotate_brother(node_t *n)
 256 {
 257     if (n == NULL || n->parent == NULL)
 258         return;
 259     if (is_first_child(n))
 260         rotate_tree(n->parent->second_child, n->birth_rotation);
 261     else
 262         rotate_tree(n->parent->first_child, n->birth_rotation);
 263 }
 264
 265 void unrotate_tree(node_t *n, rotate_t rot)
 266 {
 267     switch(rot) {
 268         case ROTATE_CLOCKWISE:
 269             rotate_tree(n, ROTATE_COUNTER_CLOCKWISE);
 270             break;
 271         case ROTATE_COUNTER_CLOCKWISE:
 272             rotate_tree(n, ROTATE_CLOCKWISE);
 273             break;
 274         case ROTATE_IDENTITY:
 275         case ROTATE_FULL_CYCLE:
 276             break;
 277     }
 278 }
 279
 280 void unrotate_brother(node_t *n)
 281 {
 282     if (n == NULL || n->parent == NULL)
 283         return;
 284     if (is_first_child(n))
 285         unrotate_tree(n->parent->second_child, n->birth_rotation);
 286     else
 287         unrotate_tree(n->parent->first_child, n->birth_rotation);
 288 }
 289
 290 void flip_tree(node_t *n, flip_t flp)
 291 {
 292     if (n == NULL || is_leaf(n))
 293         return;
 294
 295     node_t *tmp;
 296
 297     if ((flp == FLIP_HORIZONTAL && n->split_type == TYPE_HORIZONTAL)
 298             || (flp == FLIP_VERTICAL && n->split_type == TYPE_VERTICAL)) {
 299         tmp = n->first_child;
 300         n->first_child = n->second_child;
 301         n->second_child = tmp;
 302         n->split_ratio = 1.0 - n->split_ratio;
 303     }
 304
 305     flip_tree(n->first_child, flp);
 306     flip_tree(n->second_child, flp);
 307 }
 308
 309 void list_history(char *rsp)
 310 {
 311     char line[MAXLEN];
 312     for (monitor_t *m = mon_head; m != NULL; m = m->next)
 313         for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
 314             snprintf(line, sizeof(line), "%s\n", d->name);
 315             strncat(rsp, line, REMLEN(rsp));
 316             for (node_list_t *a = d->history->tail; a != NULL; a = a->prev) {
 317                 snprintf(line, sizeof(line), "  %X\n", a->node->client->window);
 318                 strncat(rsp, line, REMLEN(rsp));
 319             }
 320         }
 321 }
 322
 323 int balance_tree(node_t *n)
 324 {
 325     if (n == NULL || n->vacant) {
 326         return 0;
 327     } else if (is_leaf(n)) {
 328         return 1;
 329     } else {
 330         int b1 = balance_tree(n->first_child);
 331         int b2 = balance_tree(n->second_child);
 332         int b = b1 + b2;
 333         if (b1 > 0 && b2 > 0)
 334             n->split_ratio = (double) b1 / b;
 335         return b;
 336     }
 337 }
 338
 339 void arrange(monitor_t *m, desktop_t *d)
 340 {
 341     PRINTF("arrange %s%s%s\n", (num_monitors > 1 ? m->name : ""), (num_monitors > 1 ? " " : ""), d->name);
 342
 343     xcb_rectangle_t rect = m->rectangle;
 344     int wg = (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : window_gap);
 345     rect.x += m->left_padding + wg;
 346     rect.y += m->top_padding + wg;
 347     rect.width -= m->left_padding + m->right_padding + wg;
 348     rect.height -= m->top_padding + m->bottom_padding + wg;
 349     apply_layout(m, d, d->root, rect, rect);
 350 }
 351
 352 void apply_layout(monitor_t *m, desktop_t *d, node_t *n, xcb_rectangle_t rect, xcb_rectangle_t root_rect)
 353 {
 354     if (n == NULL)
 355         return;
 356
 357     n->rectangle = rect;
 358
 359     if (is_leaf(n)) {
 360         if (n->client->fullscreen)
 361             return;
 362
 363         if (is_floating(n->client) && n->client->border_width != border_width) {
 364             int ds = 2 * (border_width - n->client->border_width);
 365             n->client->floating_rectangle.width += ds;
 366             n->client->floating_rectangle.height += ds;
 367         }
 368
 369         if (borderless_monocle && is_tiled(n->client) && d->layout == LAYOUT_MONOCLE)
 370             n->client->border_width = 0;
 371         else
 372             n->client->border_width = border_width;
 373
 374         xcb_rectangle_t r;
 375         if (is_tiled(n->client)) {
 376             if (d->layout == LAYOUT_TILED)
 377                 r = rect;
 378             else if (d->layout == LAYOUT_MONOCLE)
 379                 r = root_rect;
 380             int wg = (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : window_gap);
 381             int bleed = wg + 2 * n->client->border_width;
 382             r.width = (bleed < r.width ? r.width - bleed : 1);
 383             r.height = (bleed < r.height ? r.height - bleed : 1);
 384             n->client->tiled_rectangle = r;
 385         } else {
 386             r = n->client->floating_rectangle;
 387         }
 388
 389         window_move_resize(n->client->window, r.x, r.y, r.width, r.height);
 390         window_border_width(n->client->window, n->client->border_width);
 391         window_draw_border(n, n == d->focus, m == mon);
 392
 393     } else {
 394         xcb_rectangle_t first_rect;
 395         xcb_rectangle_t second_rect;
 396
 397         if (n->first_child->vacant || n->second_child->vacant) {
 398             first_rect = second_rect = rect;
 399         } else {
 400             unsigned int fence;
 401             if (n->split_type == TYPE_VERTICAL) {
 402                 fence = rect.width * n->split_ratio;
 403                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
 404                 second_rect = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
 405
 406             } else if (n->split_type == TYPE_HORIZONTAL) {
 407                 fence = rect.height * n->split_ratio;
 408                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
 409                 second_rect = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
 410             }
 411         }
 412
 413         apply_layout(m, d, n->first_child, first_rect, root_rect);
 414         apply_layout(m, d, n->second_child, second_rect, root_rect);
 415     }
 416 }
 417
 418 void insert_node(monitor_t *m, desktop_t *d, node_t *n)
 419 {
 420     if (d == NULL || n == NULL)
 421         return;
 422
 423     PRINTF("insert node %X\n", n->client->window);
 424
 425     node_t *focus = d->focus;
 426
 427     if (focus == NULL) {
 428         d->root = n;
 429     } else {
 430         node_t *dad = make_node();
 431         node_t *fopar = focus->parent;
 432         n->parent = dad;
 433         dad->birth_rotation = focus->birth_rotation;
 434         switch (split_mode) {
 435             case MODE_AUTOMATIC:
 436                 if (fopar == NULL) {
 437                     dad->first_child = n;
 438                     dad->second_child = focus;
 439                     if (m->rectangle.width > m->rectangle.height)
 440                         dad->split_type = TYPE_VERTICAL;
 441                     else
 442                         dad->split_type = TYPE_HORIZONTAL;
 443                     focus->parent = dad;
 444                     d->root = dad;
 445                 } else {
 446                     node_t *grandpa = fopar->parent;
 447                     dad->parent = grandpa;
 448                     if (grandpa != NULL) {
 449                         if (is_first_child(fopar))
 450                             grandpa->first_child = dad;
 451                         else
 452                             grandpa->second_child = dad;
 453                     } else {
 454                         d->root = dad;
 455                     }
 456                     dad->split_type = fopar->split_type;
 457                     dad->split_ratio = fopar->split_ratio;
 458                     fopar->parent = dad;
 459                     rotate_t rot;
 460                     if (is_first_child(focus)) {
 461                         dad->first_child = n;
 462                         dad->second_child = fopar;
 463                         rot = ROTATE_CLOCKWISE;
 464                     } else {
 465                         dad->first_child = fopar;
 466                         dad->second_child = n;
 467                         rot = ROTATE_COUNTER_CLOCKWISE;
 468                     }
 469                     rotate_tree(fopar, rot);
 470                     n->birth_rotation = rot;
 471                 }
 472                 break;
 473             case MODE_MANUAL:
 474                 if (fopar != NULL) {
 475                     if (is_first_child(focus))
 476                         fopar->first_child = dad;
 477                     else
 478                         fopar->second_child = dad;
 479                 }
 480                 dad->split_ratio = focus->split_ratio;
 481                 dad->parent = fopar;
 482                 focus->parent = dad;
 483                 focus->birth_rotation = ROTATE_IDENTITY;
 484                 switch (split_dir) {
 485                     case DIR_LEFT:
 486                         dad->split_type = TYPE_VERTICAL;
 487                         dad->first_child = n;
 488                         dad->second_child = focus;
 489                         break;
 490                     case DIR_RIGHT:
 491                         dad->split_type = TYPE_VERTICAL;
 492                         dad->first_child = focus;
 493                         dad->second_child = n;
 494                         break;
 495                     case DIR_UP:
 496                         dad->split_type = TYPE_HORIZONTAL;
 497                         dad->first_child = n;
 498                         dad->second_child = focus;
 499                         break;
 500                     case DIR_DOWN:
 501                         dad->split_type = TYPE_HORIZONTAL;
 502                         dad->first_child = focus;
 503                         dad->second_child = n;
 504                         break;
 505                 }
 506                 if (d->root == focus)
 507                     d->root = dad;
 508                 split_mode = MODE_AUTOMATIC;
 509                 break;
 510         }
 511         if (focus->vacant)
 512             update_vacant_state(fopar);
 513     }
 514     put_status();
 515 }
 516
 517 void focus_node(monitor_t *m, desktop_t *d, node_t *n, bool is_mapped)
 518 {
 519     if (n == NULL)
 520         return;
 521
 522     PRINTF("focus node %X\n", n->client->window);
 523
 524     split_mode = MODE_AUTOMATIC;
 525     n->client->urgent = false;
 526
 527     if (is_mapped) {
 528         if (mon != m) {
 529             for (desktop_t *cd = mon->desk_head; cd != NULL; cd = cd->next)
 530                 window_draw_border(cd->focus, true, false);
 531             for (desktop_t *cd = m->desk_head; cd != NULL; cd = cd->next)
 532                 if (cd != d)
 533                     window_draw_border(cd->focus, true, true);
 534             if (d->focus == n)
 535                 window_draw_border(n, true, true);
 536         }
 537         if (d->focus != n) {
 538             window_draw_border(d->focus, false, true);
 539             window_draw_border(n, true, true);
 540         }
 541         xcb_set_input_focus(dpy, XCB_INPUT_FOCUS_POINTER_ROOT, n->client->window, XCB_CURRENT_TIME);
 542     }
 543
 544     if (d->focus != n) {
 545         d->focus = n;
 546         history_add(d->history, n);
 547     }
 548
 549     if (!is_tiled(n->client)) {
 550         if (!adaptative_raise || !might_cover(d, n))
 551             window_raise(n->client->window);
 552     } else {
 553         stack_tiled(d);
 554     }
 555
 556     if (focus_follows_pointer) {
 557         xcb_window_t win = XCB_NONE;
 558         query_pointer(&win, NULL);
 559         if (win != n->client->window)
 560             enable_motion_recorder();
 561         else
 562             disable_motion_recorder();
 563     }
 564
 565     ewmh_update_active_window();
 566 }
 567
 568 void update_current(void)
 569 {
 570     if (mon->desk->focus == NULL)
 571         ewmh_update_active_window();
 572     else
 573         focus_node(mon, mon->desk, mon->desk->focus, true);
 574 }
 575
 576 void unlink_node(desktop_t *d, node_t *n)
 577 {
 578     if (d == NULL || n == NULL)
 579         return;
 580
 581     PRINTF("unlink node %X\n", n->client->window);
 582
 583     node_t *p = n->parent;
 584
 585     if (p == NULL) {
 586         d->root = NULL;
 587         d->focus = NULL;
 588     } else {
 589         node_t *b;
 590         node_t *g = p->parent;
 591         if (is_first_child(n)) {
 592             b = p->second_child;
 593             if (!n->vacant)
 594                 unrotate_tree(b, n->birth_rotation);
 595         } else {
 596             b = p->first_child;
 597             if (!n->vacant)
 598                 unrotate_tree(b, n->birth_rotation);
 599         }
 600         b->parent = g;
 601         if (g != NULL) {
 602             if (is_first_child(p))
 603                 g->first_child = b;
 604             else
 605                 g->second_child = b;
 606         } else {
 607             d->root = b;
 608         }
 609
 610         b->birth_rotation = p->birth_rotation;
 611         n->parent = NULL;
 612         free(p);
 613
 614         if (n == d->focus)
 615             d->focus = history_get(d->history, 1);
 616
 617         update_vacant_state(b->parent);
 618     }
 619     history_remove(d->history, n);
 620     put_status();
 621 }
 622
 623 void remove_node(desktop_t *d, node_t *n)
 624 {
 625     if (d == NULL || n == NULL)
 626         return;
 627
 628     PRINTF("remove node %X\n", n->client->window);
 629
 630     unlink_node(d, n);
 631     free(n->client);
 632     free(n);
 633
 634     num_clients--;
 635     ewmh_update_client_list();
 636
 637     if (mon->desk == d)
 638         update_current();
 639 }
 640
 641 void destroy_tree(node_t *n)
 642 {
 643     if (n == NULL)
 644         return;
 645     node_t *first_tree = n->first_child;
 646     node_t *second_tree = n->second_child;
 647     if (n->client != NULL)
 648         free(n->client);
 649     free(n);
 650     destroy_tree(first_tree);
 651     destroy_tree(second_tree);
 652 }
 653
 654 void swap_nodes(node_t *n1, node_t *n2)
 655 {
 656     if (n1 == NULL || n2 == NULL || n1 == n2)
 657         return;
 658
 659     PUTS("swap nodes");
 660
 661     /* (n1 and n2 are leaves) */
 662     node_t *pn1 = n1->parent;
 663     node_t *pn2 = n2->parent;
 664     bool n1_first_child = is_first_child(n1);
 665     bool n2_first_child = is_first_child(n2);
 666     rotate_t br1 = n1->birth_rotation;
 667     rotate_t br2 = n2->birth_rotation;
 668
 669     if (pn1 != NULL) {
 670         if (n1_first_child)
 671             pn1->first_child = n2;
 672         else
 673             pn1->second_child = n2;
 674     }
 675
 676     if (pn2 != NULL) {
 677         if (n2_first_child)
 678             pn2->first_child = n1;
 679         else
 680             pn2->second_child = n1;
 681     }
 682
 683     n1->parent = pn2;
 684     n2->parent = pn1;
 685     n1->birth_rotation = br2;
 686     n2->birth_rotation = br1;
 687
 688     if (n1->vacant != n2->vacant) {
 689         update_vacant_state(n1->parent);
 690         update_vacant_state(n2->parent);
 691     }
 692
 693     /* If we ever need to generalize: */
 694     /* if (d1 != d2) { */
 695     /*     if (d1->root == n1) */
 696     /*         d1->root = n2; */
 697     /*     if (d1->focus == n1) */
 698     /*         d1->focus = n2; */
 699     /*     if (d1->last_focus == n1) */
 700     /*         d1->last_focus = n2; */
 701     /*     if (d2->root == n2) */
 702     /*         d2->root = n1; */
 703     /*     if (d2->focus == n2) */
 704     /*         d2->focus = n1; */
 705     /*     if (d2->last_focus == n2) */
 706     /*         d2->last_focus = n1; */
 707     /* } */
 708 }
 709
 710 void transfer_node(monitor_t *ms, desktop_t *ds, monitor_t *md, desktop_t *dd, node_t *n)
 711 {
 712     if (n == NULL || ds == NULL || dd == NULL || ms == NULL || md == NULL || (ms == md && dd == ds))
 713         return;
 714
 715     PRINTF("transfer node %X\n", n->client->window);
 716
 717     unlink_node(ds, n);
 718     insert_node(md, dd, n);
 719     ewmh_set_wm_desktop(n, dd);
 720
 721     if (ds == ms->desk && dd != md->desk) {
 722         if (n == ds->focus)
 723             clear_input_focus();
 724         window_hide(n->client->window);
 725     }
 726
 727     fit_monitor(md, n->client);
 728
 729     if (n->client->fullscreen)
 730         window_move_resize(n->client->window, md->rectangle.x, md->rectangle.y, md->rectangle.width, md->rectangle.height);
 731
 732     if (ds != ms->desk && dd == md->desk) {
 733         window_show(n->client->window);
 734         focus_node(md, dd, n, true);
 735     } else {
 736         focus_node(md, dd, n, false);
 737     }
 738
 739     if (ds == ms->desk || dd == md->desk)
 740         update_current();
 741 }
 742
 743 void select_monitor(monitor_t *m)
 744 {
 745     if (m == NULL || mon == m)
 746         return;
 747
 748     PRINTF("select monitor %s\n", m->name);
 749
 750     focus_node(m, m->desk, m->desk->focus, true);
 751
 752     last_mon = mon;
 753     mon = m;
 754
 755     ewmh_update_current_desktop();
 756     put_status();
 757 }
 758
 759 void select_desktop(desktop_t *d)
 760 {
 761     if (d == NULL || d == mon->desk)
 762         return;
 763
 764     PRINTF("select desktop %s\n", d->name);
 765
 766     clear_input_focus();
 767
 768     if (visible) {
 769         node_t *n = first_extrema(d->root);
 770
 771         while (n != NULL) {
 772             window_show(n->client->window);
 773             n = next_leaf(n, d->root);
 774         }
 775
 776         n = first_extrema(mon->desk->root);
 777
 778         while (n != NULL) {
 779             window_hide(n->client->window);
 780             n = next_leaf(n, mon->desk->root);
 781         }
 782     }
 783
 784     mon->last_desk = mon->desk;
 785     mon->desk = d;
 786
 787     update_current();
 788     ewmh_update_current_desktop();
 789     put_status();
 790 }
 791
 792 void cycle_monitor(cycle_dir_t dir)
 793 {
 794     if (dir == CYCLE_NEXT)
 795         select_monitor((mon->next == NULL ? mon_head : mon->next));
 796     else if (dir == CYCLE_PREV)
 797         select_monitor((mon->prev == NULL ? mon_tail : mon->prev));
 798 }
 799
 800 void cycle_desktop(monitor_t *m, desktop_t *d, cycle_dir_t dir, skip_desktop_t skip)
 801 {
 802     desktop_t *f = (dir == CYCLE_PREV ? d->prev : d->next);
 803     if (f == NULL)
 804         f = (dir == CYCLE_PREV ? m->desk_tail : m->desk_head);
 805
 806     while (f != d) {
 807         if (skip == DESKTOP_SKIP_NONE
 808                 || (skip == DESKTOP_SKIP_FREE && f->root != NULL)
 809                 || (skip == DESKTOP_SKIP_OCCUPIED && f->root == NULL)) {
 810             select_desktop(f);
 811             return;
 812         }
 813         f = (dir == CYCLE_PREV ? f->prev : f->next);
 814         if (f == NULL)
 815             f = (dir == CYCLE_PREV ? m->desk_tail : m->desk_head);
 816     }
 817 }
 818
 819 void cycle_leaf(monitor_t *m, desktop_t *d, node_t *n, cycle_dir_t dir, skip_client_t skip)
 820 {
 821     if (n == NULL)
 822         return;
 823
 824     PUTS("cycle leaf");
 825
 826     node_t *f = (dir == CYCLE_PREV ? prev_leaf(n, d->root) : next_leaf(n, d->root));
 827     if (f == NULL)
 828         f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
 829
 830     while (f != n) {
 831         bool tiled = is_tiled(f->client);
 832         if (skip == CLIENT_SKIP_NONE || (skip == CLIENT_SKIP_TILED && !tiled) || (skip == CLIENT_SKIP_FLOATING && tiled)
 833                 || (skip == CLIENT_SKIP_CLASS_DIFFER && strcmp(f->client->class_name, n->client->class_name) == 0)
 834                 || (skip == CLIENT_SKIP_CLASS_EQUAL && strcmp(f->client->class_name, n->client->class_name) != 0)) {
 835             focus_node(m, d, f, true);
 836             return;
 837         }
 838         f = (dir == CYCLE_PREV ? prev_leaf(f, d->root) : next_leaf(f, d->root));
 839         if (f == NULL)
 840             f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
 841     }
 842 }
 843
 844 void nearest_leaf(monitor_t *m, desktop_t *d, node_t *n, nearest_arg_t dir, skip_client_t skip)
 845 {
 846     if (n == NULL)
 847         return;
 848
 849     PUTS("nearest leaf");
 850
 851     node_t *x = NULL;
 852
 853     for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root))
 854         if (skip == CLIENT_SKIP_NONE || (skip == CLIENT_SKIP_TILED && !is_tiled(f->client)) || (skip == CLIENT_SKIP_FLOATING && is_tiled(f->client))
 855                 || (skip == CLIENT_SKIP_CLASS_DIFFER && strcmp(f->client->class_name, n->client->class_name) == 0)
 856                 || (skip == CLIENT_SKIP_CLASS_EQUAL && strcmp(f->client->class_name, n->client->class_name) != 0))
 857             if ((dir == NEAREST_OLDER
 858                         && (f->client->uid < n->client->uid)
 859                         && (x == NULL || f->client->uid > x->client->uid))
 860                     || (dir == NEAREST_NEWER
 861                         && (f->client->uid > n->client->uid)
 862                         && (x == NULL || f->client->uid < x->client->uid)))
 863                 x = f;
 864
 865     focus_node(m, d, x, true);
 866 }
 867
 868 void circulate_leaves(monitor_t *m, desktop_t *d, circulate_dir_t dir) {
 869     if (d == NULL || d->root == NULL || is_leaf(d->root))
 870         return;
 871     node_t *par = d->focus->parent;
 872     bool focus_first_child = is_first_child(d->focus);
 873     if (dir == CIRCULATE_FORWARD)
 874         for (node_t *s = second_extrema(d->root), *f = prev_leaf(s, d->root); f != NULL; s = prev_leaf(f, d->root), f = prev_leaf(s, d->root))
 875             swap_nodes(f, s);
 876     else
 877         for (node_t *f = first_extrema(d->root), *s = next_leaf(f, d->root); s != NULL; f = next_leaf(s, d->root), s = next_leaf(f, d->root))
 878             swap_nodes(f, s);
 879     if (focus_first_child)
 880         focus_node(m, d, par->first_child, true);
 881     else
 882         focus_node(m, d, par->second_child, true);
 883 }
 884
 885 void update_vacant_state(node_t *n)
 886 {
 887     if (n == NULL)
 888         return;
 889
 890     PUTS("update vacant state");
 891
 892     /* n is not a leaf */
 893     node_t *p = n;
 894
 895     while (p != NULL) {
 896         p->vacant = (p->first_child->vacant && p->second_child->vacant);
 897         p = p->parent;
 898     }
 899 }
 900
 901 void fit_monitor(monitor_t *m, client_t *c)
 902 {
 903     xcb_rectangle_t crect = c->floating_rectangle;
 904     xcb_rectangle_t mrect = m->rectangle;
 905     while (crect.x < mrect.x)
 906         crect.x += mrect.width;
 907     while (crect.x > (mrect.x + mrect.width - 1))
 908         crect.x -= mrect.width;
 909     while (crect.y < mrect.y)
 910         crect.y += mrect.height;
 911     while (crect.y > (mrect.y + mrect.height - 1))
 912         crect.y -= mrect.height;
 913     c->floating_rectangle = crect;
 914 }
 915
 916 void put_status(void)
 917 {
 918     if (status_fifo == NULL)
 919         return;
 920     if (status_prefix != NULL)
 921         fprintf(status_fifo, "%s", status_prefix);
 922     bool urgent = false;
 923     for (monitor_t *m = mon_head; m != NULL; m = m->next) {
 924         fprintf(status_fifo, "%c%s:", (mon == m ? 'M' : 'm'), m->name);
 925         for (desktop_t *d = m->desk_head; d != NULL; d = d->next, urgent = false) {
 926             for (node_t *n = first_extrema(d->root); n != NULL && !urgent; n = next_leaf(n, d->root))
 927                 urgent |= n->client->urgent;
 928             fprintf(status_fifo, "%c%s:", m->desk == d ? (urgent ? 'U' : 'D') : (d->root == NULL ? 'E' : (urgent ? 'u' : 'd')), d->name);
 929         }
 930     }
 931     fprintf(status_fifo, "L%s\n", (mon->desk->layout == LAYOUT_TILED ? "tiled" : "monocle"));
 932     fflush(status_fifo);
 933 }
 934
 935 void list_monitors(list_option_t opt, char *rsp)
 936 {
 937     char line[MAXLEN];
 938     for (monitor_t *m = mon_head; m != NULL; m = m->next) {
 939         snprintf(line, sizeof(line), "%s %ux%u%+i%+i", m->name, m->rectangle.width, m->rectangle.height, m->rectangle.x, m->rectangle.y);
 940         strncat(rsp, line, REMLEN(rsp));
 941         if (m == mon)
 942             strncat(rsp, " #\n", REMLEN(rsp));
 943         else if (m == last_mon)
 944             strncat(rsp, " ~\n", REMLEN(rsp));
 945         else
 946             strncat(rsp, "\n", REMLEN(rsp));
 947         if (opt == LIST_OPTION_VERBOSE)
 948             list_desktops(m, opt, 1, rsp);
 949     }
 950 }
 951
 952 void list_desktops(monitor_t *m, list_option_t opt, unsigned int depth, char *rsp)
 953 {
 954     char line[MAXLEN];
 955     for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
 956         for (unsigned int i = 0; i < depth; i++)
 957             strncat(rsp, "  ", REMLEN(rsp));
 958         snprintf(line, sizeof(line), "%s %c", d->name, (d->layout == LAYOUT_TILED ? 'T' : 'M'));
 959         strncat(rsp, line, REMLEN(rsp));
 960         if (d == m->desk)
 961             strncat(rsp, " @\n", REMLEN(rsp));
 962         else if (d == m->last_desk)
 963             strncat(rsp, " ~\n", REMLEN(rsp));
 964         else
 965             strncat(rsp, "\n", REMLEN(rsp));
 966         if (opt == LIST_OPTION_VERBOSE)
 967             list(d, d->root, rsp, depth + 1);
 968     }
 969 }
 970
 971 void list(desktop_t *d, node_t *n, char *rsp, unsigned int depth)
 972 {
 973     if (n == NULL)
 974         return;
 975
 976     char line[MAXLEN];
 977
 978     for (unsigned int i = 0; i < depth; i++)
 979         strncat(rsp, "  ", REMLEN(rsp));
 980
 981     if (is_leaf(n)) {
 982         client_t *c = n->client;
 983         snprintf(line, sizeof(line), "%c %s %X %u %u %ux%u%+i%+i %c%c%c%c%c", (n->birth_rotation == ROTATE_CLOCKWISE ? 'a' : (n->birth_rotation == ROTATE_COUNTER_CLOCKWISE ? 'c' : 'm')), c->class_name, c->window, c->uid, c->border_width, c->floating_rectangle.width, c->floating_rectangle.height, c->floating_rectangle.x, c->floating_rectangle.y, (c->floating ? 'f' : '-'), (c->transient ? 't' : '-'), (c->fullscreen ? 'F' : '-'), (c->urgent ? 'u' : '-'), (c->locked ? 'l' : '-'));
 984     } else {
 985         snprintf(line, sizeof(line), "%c %c %.2f", (n->split_type == TYPE_HORIZONTAL ? 'H' : 'V'), (n->birth_rotation == ROTATE_CLOCKWISE ? 'a' : (n->birth_rotation == ROTATE_COUNTER_CLOCKWISE ? 'c' : 'm')), n->split_ratio);
 986     }
 987
 988     strncat(rsp, line, REMLEN(rsp));
 989
 990     if (n == d->focus)
 991         strncat(rsp, " *\n", REMLEN(rsp));
 992     else
 993         strncat(rsp, "\n", REMLEN(rsp));
 994
 995     list(d, n->first_child, rsp, depth + 1);
 996     list(d, n->second_child, rsp, depth + 1);
 997 }
 998
 999 void restore_layout(char *file_path)
1000 {
1001     if (file_path == NULL)
1002         return;
1003
1004     FILE *snapshot = fopen(file_path, "r");
1005     if (snapshot == NULL) {
1006         warn("restore: can't open file\n");
1007         return;
1008     }
1009
1010     char line[MAXLEN];
1011     monitor_t *m = NULL;
1012     desktop_t *d = NULL;
1013     node_t *n = NULL;
1014     num_clients = 0;
1015     unsigned int level, last_level = 0, max_uid = 0;
1016     bool aborted = false;
1017
1018     while (!aborted && fgets(line, sizeof(line), snapshot) != NULL) {
1019         unsigned int len = strlen(line);
1020         level = 0;
1021         while (level < strlen(line) && isspace(line[level]))
1022             level++;
1023         if (level == 0) {
1024             if (m == NULL)
1025                 m = mon_head;
1026             else
1027                 m = m->next;
1028             if (len >= 2)
1029                 switch (line[len - 2]) {
1030                     case '#':
1031                         mon = m;
1032                         break;
1033                     case '~':
1034                         last_mon = m;
1035                         break;
1036                 }
1037         } else if (level == 2) {
1038             if (d == NULL)
1039                 d = m->desk_head;
1040             else
1041                 d = d->next;
1042             int i = len - 1;
1043             while (i > 0 && !isupper(line[i]))
1044                 i--;
1045             if (line[i] == 'M')
1046                 d->layout = LAYOUT_MONOCLE;
1047             else if (line[i] == 'T')
1048                 d->layout = LAYOUT_TILED;
1049             if (len >= 2)
1050                 switch (line[len - 2]) {
1051                     case '@':
1052                         m->desk = d;
1053                         break;
1054                     case '~':
1055                         m->last_desk = d;
1056                         break;
1057                 }
1058         } else {
1059             node_t *birth = make_node();
1060             if (level == 4) {
1061                 empty_desktop(d);
1062                 d->root = birth;
1063             } else {
1064                 if (level > last_level) {
1065                     n->first_child = birth;
1066                 } else {
1067                     do {
1068                         n = n->parent;
1069                     } while (n != NULL && n->second_child != NULL);
1070                     if (n == NULL) {
1071                         warn("restore: file is malformed\n");
1072                         aborted = true;
1073                     }
1074                     n->second_child = birth;
1075                 }
1076                 birth->parent = n;
1077             }
1078             n = birth;
1079
1080             char br;
1081             if (isupper(line[level])) {
1082                 char st;
1083                 sscanf(line + level, "%c %c %lf", &st, &br, &n->split_ratio);
1084                 if (st == 'H')
1085                     n->split_type = TYPE_HORIZONTAL;
1086                 else if (st == 'V')
1087                     n->split_type = TYPE_VERTICAL;
1088             } else {
1089                 client_t *c = make_client(XCB_NONE);
1090                 num_clients++;
1091                 char floating, transient, fullscreen, urgent, locked;
1092                 sscanf(line + level, "%c %s %X %u %u %hux%hu%hi%hi %c%c%c%c%c", &br, c->class_name, &c->window, &c->uid, &c->border_width, &c->floating_rectangle.width, &c->floating_rectangle.height, &c->floating_rectangle.x, &c->floating_rectangle.y, &floating, &transient, &fullscreen, &urgent, &locked);
1093                 c->floating = (floating == '-' ? false : true);
1094                 c->transient = (transient == '-' ? false : true);
1095                 c->fullscreen = (fullscreen == '-' ? false : true);
1096                 c->urgent = (urgent == '-' ? false : true);
1097                 c->locked = (locked == '-' ? false : true);
1098                 if (c->uid > max_uid)
1099                     max_uid = c->uid;
1100                 n->client = c;
1101                 if (len >= 2 && line[len - 2] == '*')
1102                     d->focus = n;
1103             }
1104             if (br == 'a')
1105                 n->birth_rotation = ROTATE_CLOCKWISE;
1106             else if (br == 'c')
1107                 n->birth_rotation = ROTATE_COUNTER_CLOCKWISE;
1108             else if (br == 'm')
1109                 n->birth_rotation = ROTATE_IDENTITY;
1110         }
1111         last_level = level;
1112     }
1113
1114     fclose(snapshot);
1115
1116     if (!aborted) {
1117         client_uid = max_uid + 1;
1118         for (monitor_t *m = mon_head; m != NULL; m = m->next)
1119             for (desktop_t *d = m->desk_head; d != NULL; d = d->next)
1120                 for (node_t *n = first_extrema(d->root); n != NULL; n = next_leaf(n, d->root)) {
1121                     uint32_t values[] = {(focus_follows_pointer ? CLIENT_EVENT_MASK_FFP : CLIENT_EVENT_MASK)};
1122                     xcb_change_window_attributes(dpy, n->client->window, XCB_CW_EVENT_MASK, values);
1123                     if (n->client->floating) {
1124                         n->vacant = true;
1125                         update_vacant_state(n->parent);
1126                     }
1127                 }
1128         ewmh_update_current_desktop();
1129     }
1130 }
1131
1132 void restore_history(char *file_path)
1133 {
1134     if (file_path == NULL)
1135         return;
1136
1137     FILE *snapshot = fopen(file_path, "r");
1138     if (snapshot == NULL) {
1139         warn("restore history: can't open file\n");
1140         return;
1141     }
1142
1143     char line[MAXLEN];
1144     desktop_t *d = NULL;
1145     unsigned int level;
1146
1147     while (fgets(line, sizeof(line), snapshot) != NULL) {
1148         unsigned int i = strlen(line) - 1;
1149         while (i > 0 && isspace(line[i]))
1150             line[i--] = '\0';
1151         level = 0;
1152         while (level < strlen(line) && isspace(line[level]))
1153             level++;
1154         PRINTF("level %u: %s\n", level, line + level);
1155         if (level == 0) {
1156             desktop_location_t loc;
1157             if (locate_desktop(line + level, &loc))
1158                 d = loc.desktop;
1159         } else if (d != NULL) {
1160             xcb_window_t win;
1161             if (sscanf(line + level, "%X", &win) == 1) {
1162                 window_location_t loc;
1163                 if (locate_window(win, &loc))
1164                     history_add(d->history, loc.node);
1165             }
1166         }
1167     }
1168
1169     fclose(snapshot);
1170 }