tree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <math.h>
   5 #include <xcb/xcb.h>
   6 #include <xcb/xcb_event.h>
   7 #include "settings.h"
   8 #include "helpers.h"
   9 #include "window.h"
  10 #include "types.h"
  11 #include "bspwm.h"
  12 #include "ewmh.h"
  13 #include "tree.h"
  14
  15 bool is_leaf(node_t *n)
  16 {
  17     return (n != NULL && n->first_child == NULL && n->second_child == NULL);
  18 }
  19
  20 bool is_tiled(client_t *c)
  21 {
  22     if (c == NULL)
  23         return false;
  24     return (!c->floating && !c->transient && !c->fullscreen);
  25 }
  26
  27 bool is_floating(client_t *c)
  28 {
  29     if (c == NULL)
  30         return false;
  31     return (c->floating && !c->fullscreen);
  32 }
  33
  34 bool is_first_child(node_t *n)
  35 {
  36     return (n != NULL && n->parent != NULL && n->parent->first_child == n);
  37 }
  38
  39 bool is_second_child(node_t *n)
  40 {
  41     return (n != NULL && n->parent != NULL && n->parent->second_child == n);
  42 }
  43
  44 void change_split_ratio(node_t *n, value_change_t chg) {
  45     n->split_ratio = pow(n->split_ratio, (chg == CHANGE_INCREASE ? INC_EXP : DEC_EXP));
  46 }
  47
  48 node_t *first_extrema(node_t *n)
  49 {
  50     if (n == NULL)
  51         return NULL;
  52     else if (n->first_child == NULL)
  53         return n;
  54     else
  55         return first_extrema(n->first_child);
  56 }
  57
  58 node_t *second_extrema(node_t *n)
  59 {
  60     if (n == NULL)
  61         return NULL;
  62     else if (n->second_child == NULL)
  63         return n;
  64     else
  65         return second_extrema(n->second_child);
  66 }
  67
  68 node_t *next_leaf(node_t *n)
  69 {
  70     if (n == NULL)
  71         return NULL;
  72     node_t *p = n;
  73     while (is_second_child(p))
  74         p = p->parent;
  75     if (p->parent == NULL)
  76         return NULL;
  77     return first_extrema(p->parent->second_child);
  78 }
  79
  80 node_t *prev_leaf(node_t *n)
  81 {
  82     if (n == NULL)
  83         return NULL;
  84     node_t *p = n;
  85     while (is_first_child(p))
  86         p = p->parent;
  87     if (p->parent == NULL)
  88         return NULL;
  89     return second_extrema(p->parent->first_child);
  90 }
  91
  92 node_t *find_fence(node_t *n, direction_t dir)
  93 {
  94     node_t *p;
  95
  96     if (n == NULL)
  97         return NULL;
  98
  99     p = n->parent;
 100
 101     while (p != NULL) {
 102         if ((dir == DIR_UP && p->split_type == TYPE_HORIZONTAL && p->rectangle.y < n->rectangle.y)
 103                 || (dir == DIR_LEFT && p->split_type == TYPE_VERTICAL && p->rectangle.x < n->rectangle.x)
 104                 || (dir == DIR_DOWN && p->split_type == TYPE_HORIZONTAL && (p->rectangle.y + p->rectangle.height) > (n->rectangle.y + n->rectangle.height))
 105                 || (dir == DIR_RIGHT && p->split_type == TYPE_VERTICAL && (p->rectangle.x + p->rectangle.width) > (n->rectangle.x + n->rectangle.width)))
 106             return p;
 107         p = p->parent;
 108     }
 109
 110     return NULL;
 111 }
 112
 113 node_t *find_neighbor(node_t *n, direction_t dir)
 114 {
 115     node_t *fence = find_fence(n, dir);
 116
 117     if (fence == NULL)
 118         return NULL;
 119
 120     if (dir == DIR_UP || dir == DIR_LEFT)
 121         return second_extrema(fence->first_child);
 122     else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 123         return first_extrema(fence->second_child);
 124
 125     return NULL;
 126 }
 127
 128 void move_fence(node_t *n, direction_t dir, fence_move_t mov)
 129 {
 130     node_t *fence = find_fence(n, dir);
 131
 132     if (fence == NULL)
 133         return;
 134
 135     if ((mov == MOVE_PUSH && (dir == DIR_RIGHT || dir == DIR_DOWN))
 136             || (mov == MOVE_PULL && (dir == DIR_LEFT || dir == DIR_UP)))
 137         change_split_ratio(fence, CHANGE_INCREASE);
 138     else
 139         change_split_ratio(fence, CHANGE_DECREASE);
 140 }
 141
 142 void rotate_tree(node_t *n, rotate_t rot)
 143 {
 144     if (n == NULL || is_leaf(n))
 145         return;
 146
 147     node_t *tmp;
 148
 149     if ((rot == ROTATE_CLOCKWISE && n->split_type == TYPE_HORIZONTAL)
 150             || (rot == ROTATE_COUNTER_CLOCKWISE && n->split_type == TYPE_VERTICAL)
 151             || rot == ROTATE_FULL_CYCLE) {
 152         tmp = n->first_child;
 153         n->first_child = n->second_child;
 154         n->second_child = tmp;
 155         n->split_ratio = 1.0 - n->split_ratio;
 156     }
 157
 158     if (rot != ROTATE_FULL_CYCLE) {
 159         if (n->split_type == TYPE_HORIZONTAL)
 160             n->split_type = TYPE_VERTICAL;
 161         else if (n->split_type == TYPE_VERTICAL)
 162             n->split_type = TYPE_HORIZONTAL;
 163     }
 164
 165     rotate_tree(n->first_child, rot);
 166     rotate_tree(n->second_child, rot);
 167 }
 168
 169 void magnetise_tree(node_t *n, corner_t corner)
 170 {
 171     if (n == NULL || is_leaf(n))
 172         return;
 173
 174     PUTS("magnetise tree");
 175
 176     switch (n->split_type) {
 177         case TYPE_HORIZONTAL:
 178             if (corner == TOP_LEFT || corner == TOP_RIGHT)
 179                 change_split_ratio(n, CHANGE_DECREASE);
 180             else
 181                 change_split_ratio(n, CHANGE_INCREASE);
 182             break;
 183         case TYPE_VERTICAL:
 184             if (corner == TOP_LEFT || corner == BOTTOM_LEFT)
 185                 change_split_ratio(n, CHANGE_DECREASE);
 186             else
 187                 change_split_ratio(n, CHANGE_INCREASE);
 188             break;
 189         default:
 190             break;
 191     }
 192
 193     magnetise_tree(n->first_child, corner);
 194     magnetise_tree(n->second_child, corner);
 195 }
 196
 197 void dump_tree(desktop_t *d, node_t *n, char *rsp, int depth)
 198 {
 199     if (n == NULL)
 200         return;
 201
 202     char line[MAXLEN];
 203
 204     for (int i = 0; i < depth; i++)
 205         strncat(rsp, "  ", REMLEN(rsp));
 206
 207     if (is_leaf(n))
 208         snprintf(line, sizeof(line), "%s %X %s%s%s%s%s", n->client->class_name, n->client->window, (n->client->floating ? "f" : "-"), (n->client->transient ? "t" : "-"), (n->client->fullscreen ? "F" : "-"), (n->client->urgent ? "u" : "-"), (n->client->locked ? "l" : "-"));
 209     else
 210         snprintf(line, sizeof(line), "%s %.2f", (n->split_type == TYPE_HORIZONTAL ? "H" : "V"), n->split_ratio);
 211
 212     strncat(rsp, line, REMLEN(rsp));
 213
 214     if (n == d->focus)
 215         strncat(rsp, " *\n", REMLEN(rsp));
 216     else
 217         strncat(rsp, "\n", REMLEN(rsp));
 218
 219     dump_tree(d, n->first_child, rsp, depth + 1);
 220     dump_tree(d, n->second_child, rsp, depth + 1);
 221 }
 222
 223 void refresh_current(void) {
 224     if (desk->focus == NULL)
 225         ewmh_update_active_window();
 226     else
 227         focus_node(desk, desk->focus, true);
 228 }
 229
 230 void list_desktops(char *rsp)
 231 {
 232     desktop_t *d = desk_head;
 233
 234     while (d != NULL) {
 235         strncat(rsp, d->name, REMLEN(rsp));
 236         if (desk == d)
 237             strncat(rsp, " @\n", REMLEN(rsp));
 238         else
 239             strncat(rsp, "\n", REMLEN(rsp));
 240         dump_tree(d, d->root, rsp, 1);
 241         d = d->next;
 242     }
 243 }
 244
 245 void update_root_dimensions(void)
 246 {
 247     root_rect.x = left_padding + window_gap;
 248     root_rect.y = top_padding + window_gap;
 249     root_rect.width = screen_width - (left_padding + right_padding + window_gap);
 250     root_rect.height = screen_height - (top_padding + bottom_padding + window_gap);
 251 }
 252
 253 void apply_layout(desktop_t *d, node_t *n, xcb_rectangle_t rect)
 254 {
 255     if (d == NULL || n == NULL)
 256         return;
 257
 258     n->rectangle = rect;
 259
 260     if (is_leaf(n)) {
 261         if (n->client->fullscreen)
 262             return;
 263
 264         if (borderless_monocle && is_tiled(n->client) && d->layout == LAYOUT_MONOCLE)
 265             n->client->border_width = 0;
 266         else
 267             n->client->border_width = border_width;
 268
 269         xcb_rectangle_t r;
 270         if (is_tiled(n->client)) {
 271             if (d->layout == LAYOUT_TILED)
 272                 r = rect;
 273             else if (d->layout == LAYOUT_MONOCLE)
 274                 r = root_rect;
 275             int bleed = window_gap + 2 * n->client->border_width;
 276             r.width = (bleed < r.width ? r.width - bleed : 1);
 277             r.height = (bleed < r.height ? r.height - bleed : 1);
 278             n->client->tiled_rectangle = r;
 279         } else {
 280             r = n->client->floating_rectangle;
 281         }
 282
 283         window_move_resize(n->client->window, r.x, r.y, r.width, r.height);
 284         window_border_width(n->client->window, n->client->border_width);
 285         window_draw_border(n, n == d->focus);
 286
 287         if (d->layout == LAYOUT_MONOCLE && n == d->focus)
 288             window_raise(n->client->window);
 289
 290     } else {
 291         xcb_rectangle_t first_rect;
 292         xcb_rectangle_t second_rect;
 293
 294         if (n->first_child->vacant || n->second_child->vacant) {
 295             first_rect = second_rect = rect;
 296         } else {
 297             unsigned int fence;
 298             if (n->split_type == TYPE_VERTICAL) {
 299                 fence = rect.width * n->split_ratio;
 300                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
 301                 second_rect = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
 302
 303             } else if (n->split_type == TYPE_HORIZONTAL) {
 304                 fence = rect.height * n->split_ratio;
 305                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
 306                 second_rect = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
 307             }
 308         }
 309
 310         apply_layout(d, n->first_child, first_rect);
 311         apply_layout(d, n->second_child, second_rect);
 312     }
 313 }
 314
 315 void insert_node(desktop_t *d, node_t *n)
 316 {
 317     if (d == NULL || n == NULL)
 318         return;
 319
 320     PRINTF("insert node %X\n", n->client->window);
 321
 322     node_t *focus = d->focus;
 323
 324     if (focus == NULL) {
 325         d->root = n;
 326     } else {
 327         node_t *dad = make_node();
 328         node_t *fopar = focus->parent;
 329         n->parent = dad;
 330         n->born_as = split_mode;
 331         switch (split_mode) {
 332             case MODE_AUTOMATIC:
 333                 if (fopar == NULL) {
 334                     dad->first_child = n;
 335                     dad->second_child = focus;
 336                     if (focus->rectangle.width > focus->rectangle.height)
 337                         dad->split_type = TYPE_VERTICAL;
 338                     else
 339                         dad->split_type = TYPE_HORIZONTAL;
 340                     focus->parent = dad;
 341                     d->root = dad;
 342                 } else {
 343                     node_t *grandpa = fopar->parent;
 344                     dad->parent = grandpa;
 345                     if (grandpa != NULL) {
 346                         if (is_first_child(fopar))
 347                             grandpa->first_child = dad;
 348                         else
 349                             grandpa->second_child = dad;
 350                     } else {
 351                         d->root = dad;
 352                     }
 353                     dad->split_type = fopar->split_type;
 354                     dad->split_ratio = fopar->split_ratio;
 355                     fopar->parent = dad;
 356                     if (is_first_child(focus)) {
 357                         dad->first_child = n;
 358                         dad->second_child = fopar;
 359                         rotate_tree(fopar, ROTATE_CLOCKWISE);
 360                     } else {
 361                         dad->first_child = fopar;
 362                         dad->second_child = n;
 363                         rotate_tree(fopar, ROTATE_COUNTER_CLOCKWISE);
 364                     }
 365                 }
 366                 break;
 367             case MODE_MANUAL:
 368                 if (fopar != NULL) {
 369                     if (is_first_child(focus))
 370                         fopar->first_child = dad;
 371                     else
 372                         fopar->second_child = dad;
 373                 }
 374                 dad->split_ratio = focus->split_ratio;
 375                 dad->parent = fopar;
 376                 focus->parent = dad;
 377                 switch (split_dir) {
 378                     case DIR_LEFT:
 379                         dad->split_type = TYPE_VERTICAL;
 380                         dad->first_child = n;
 381                         dad->second_child = focus;
 382                         break;
 383                     case DIR_RIGHT:
 384                         dad->split_type = TYPE_VERTICAL;
 385                         dad->first_child = focus;
 386                         dad->second_child = n;
 387                         break;
 388                     case DIR_UP:
 389                         dad->split_type = TYPE_HORIZONTAL;
 390                         dad->first_child = n;
 391                         dad->second_child = focus;
 392                         break;
 393                     case DIR_DOWN:
 394                         dad->split_type = TYPE_HORIZONTAL;
 395                         dad->first_child = focus;
 396                         dad->second_child = n;
 397                         break;
 398                 }
 399                 if (d->root == focus)
 400                     d->root = dad;
 401                 split_mode = MODE_AUTOMATIC;
 402                 break;
 403         }
 404         if (focus->vacant)
 405             update_vacant_state(fopar);
 406     }
 407 }
 408
 409 void focus_node(desktop_t *d, node_t *n, bool is_mapped)
 410 {
 411     if (n == NULL)
 412         return;
 413
 414     PRINTF("focus node %X\n", n->client->window);
 415
 416     split_mode = MODE_AUTOMATIC;
 417     n->client->urgent = false;
 418
 419     if (is_mapped) {
 420         if (d->focus != n) {
 421             window_draw_border(d->focus, false);
 422             window_draw_border(n, true);
 423         }
 424         xcb_set_input_focus(dpy, XCB_INPUT_FOCUS_POINTER_ROOT, n->client->window, XCB_CURRENT_TIME);
 425     }
 426
 427     if (!is_tiled(n->client) || d->layout == LAYOUT_MONOCLE)
 428         window_raise(n->client->window);
 429     else if (is_tiled(n->client))
 430         window_lower(n->client->window);
 431
 432     if (d->focus != n) {
 433         d->last_focus = d->focus;
 434         d->focus = n;
 435     }
 436
 437     ewmh_update_active_window();
 438 }
 439
 440 void update_current(void)
 441 {
 442     if (desk->focus == NULL)
 443         ewmh_update_active_window();
 444     else
 445         focus_node(desk, desk->focus, true);
 446 }
 447
 448 void unlink_node(desktop_t *d, node_t *n)
 449 {
 450     if (d == NULL || n == NULL)
 451         return;
 452
 453     PRINTF("unlink node %X\n", n->client->window);
 454
 455     node_t *p = n->parent;
 456
 457     if (p == NULL) {
 458         d->root = NULL;
 459         d->focus = NULL;
 460         d->last_focus = NULL;
 461     } else {
 462         node_t *b;
 463         node_t *g = p->parent;
 464         bool n_first_child = is_first_child(n);
 465         if (n_first_child) {
 466             b = p->second_child;
 467             if (n->born_as == MODE_AUTOMATIC)
 468                 rotate_tree(b, ROTATE_COUNTER_CLOCKWISE);
 469         } else {
 470             b = p->first_child;
 471             if (n->born_as == MODE_AUTOMATIC)
 472                 rotate_tree(b, ROTATE_CLOCKWISE);
 473         }
 474         b->parent = g;
 475         if (g != NULL) {
 476             if (is_first_child(p))
 477                 g->first_child = b;
 478             else
 479                 g->second_child = b;
 480         } else {
 481             d->root = b;
 482         }
 483
 484         n->parent = NULL;
 485         free(p);
 486
 487         if (n == d->last_focus) {
 488             d->last_focus = NULL;
 489         } else if (n == d->focus) {
 490             if (d->last_focus != NULL)
 491                 d->focus = d->last_focus;
 492             else
 493                 d->focus = (n_first_child ? first_extrema(b) : second_extrema(b));
 494             d->last_focus = NULL;
 495         }
 496
 497         update_vacant_state(b->parent);
 498     }
 499 }
 500
 501 void remove_node(desktop_t *d, node_t *n)
 502 {
 503     if (d == NULL || n == NULL)
 504         return;
 505
 506     PRINTF("remove node %X\n", n->client->window);
 507
 508     unlink_node(d, n);
 509     free(n->client);
 510     free(n);
 511
 512     num_clients--;
 513     ewmh_update_client_list();
 514
 515     if (desk == d)
 516         update_current();
 517 }
 518
 519 void swap_nodes(node_t *n1, node_t *n2)
 520 {
 521     if (n1 == NULL || n2 == NULL || n1 == n2)
 522         return;
 523
 524     PUTS("swap nodes");
 525
 526     /* (n1 and n2 are leaves) */
 527     node_t *pn1 = n1->parent;
 528     node_t *pn2 = n2->parent;
 529     bool n1_first_child = is_first_child(n1);
 530     bool n2_first_child = is_first_child(n2);
 531
 532     if (pn1 != NULL) {
 533         if (n1_first_child)
 534             pn1->first_child = n2;
 535         else
 536             pn1->second_child = n2;
 537     }
 538
 539     if (pn2 != NULL) {
 540         if (n2_first_child)
 541             pn2->first_child = n1;
 542         else
 543             pn2->second_child = n1;
 544     }
 545
 546     n1->parent = pn2;
 547     n2->parent = pn1;
 548
 549     if (n1->vacant != n2->vacant) {
 550         update_vacant_state(n1->parent);
 551         update_vacant_state(n2->parent);
 552     }
 553 }
 554
 555 void transfer_node(desktop_t *ds, desktop_t *dd, node_t *n)
 556 {
 557     if (n == NULL || ds == NULL || dd == NULL || dd == ds)
 558         return;
 559
 560     PRINTF("transfer node %X\n", n->client->window);
 561
 562     unlink_node(ds, n);
 563
 564     if (ds == desk) {
 565         window_hide(n->client->window);
 566     }
 567
 568     insert_node(dd, n);
 569
 570     if (dd == desk) {
 571         window_show(n->client->window);
 572         focus_node(dd, n, true);
 573     } else {
 574         focus_node(dd, n, false);
 575     }
 576
 577     if (ds == desk || dd == desk)
 578         update_current();
 579 }
 580
 581 void select_desktop(desktop_t *d)
 582 {
 583     if (d == NULL || d == desk)
 584         return;
 585
 586     PRINTF("select desktop %s\n", d->name);
 587
 588     node_t *n = first_extrema(d->root);
 589
 590     while (n != NULL) {
 591         window_show(n->client->window);
 592         n = next_leaf(n);
 593     }
 594
 595     n = first_extrema(desk->root);
 596
 597     while (n != NULL) {
 598         window_hide(n->client->window);
 599         n = next_leaf(n);
 600     }
 601
 602     last_desk = desk;
 603     desk = d;
 604
 605     update_current();
 606     ewmh_update_current_desktop();
 607 }
 608
 609 void cycle_desktop(cycle_dir_t dir)
 610 {
 611     if (dir == CYCLE_NEXT)
 612         select_desktop((desk->next == NULL ? desk_head : desk->next));
 613     else if (dir == CYCLE_PREV)
 614         select_desktop((desk->prev == NULL ? desk_tail : desk->prev));
 615 }
 616
 617 void cycle_leaf(desktop_t *d, node_t *n, cycle_dir_t dir, skip_client_t skip)
 618 {
 619     if (n == NULL)
 620         return;
 621
 622     PUTS("cycle leaf");
 623
 624     node_t *f = (dir == CYCLE_PREV ? prev_leaf(n) : next_leaf(n));
 625     if (f == NULL)
 626         f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
 627
 628     while (f != n) {
 629         bool tiled = is_tiled(f->client);
 630         if (skip == SKIP_NONE || (skip == SKIP_TILED && !tiled) || (skip == SKIP_FLOATING && tiled)
 631                 || (skip == SKIP_CLASS_DIFFER && strcmp(f->client->class_name, n->client->class_name) == 0)
 632                 || (skip == SKIP_CLASS_EQUAL && strcmp(f->client->class_name, n->client->class_name) != 0)) {
 633             focus_node(d, f, true);
 634             return;
 635         }
 636         f = (dir == CYCLE_PREV ? prev_leaf(f) : next_leaf(f));
 637         if (f == NULL)
 638             f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
 639     }
 640 }
 641
 642 void update_vacant_state(node_t *n)
 643 {
 644     if (n == NULL)
 645         return;
 646
 647     PUTS("update vacant state");
 648
 649     /* n is not a leaf */
 650     node_t *p = n;
 651
 652     while (p != NULL) {
 653         p->vacant = (p->first_child->vacant && p->second_child->vacant);
 654         p = p->parent;
 655     }
 656 }
 657
 658 desktop_t *find_desktop(char *name)
 659 {
 660     desktop_t *d = desk_head;
 661     while (d != NULL) {
 662         if (strcmp(d->name, name) == 0)
 663             return d;
 664         d = d->next;
 665     }
 666     return NULL;
 667 }
 668
 669 void add_desktop(char *name)
 670 {
 671     desktop_t *d = make_desktop(name);
 672     desk_tail->next = d;
 673     d->prev = desk_tail;
 674     desk_tail = d;
 675     num_desktops++;
 676     ewmh_update_number_of_desktops();
 677     ewmh_update_desktop_names();
 678 }