tree.c

   1 #include <stdio.h>
   2 #include <math.h>
   3 #include <xcb/xcb.h>
   4 #include <xcb/xcb_event.h>
   5 #include "settings.h"
   6 #include "helpers.h"
   7 #include "utils.h"
   8 #include "types.h"
   9 #include "bspwm.h"
  10 #include "tree.h"
  11
  12 bool is_leaf(node_t *n)
  13 {
  14     return (n != NULL && n->first_child == NULL && n->second_child == NULL);
  15 }
  16
  17 bool is_first_child(node_t *n)
  18 {
  19     return (n != NULL && n->parent != NULL && n->parent->first_child == n);
  20 }
  21
  22 bool is_second_child(node_t *n)
  23 {
  24     return (n != NULL && n->parent != NULL && n->parent->second_child == n);
  25 }
  26
  27
  28 void change_split_ratio(node_t *n, value_change_t chg) {
  29     n->split_ratio = pow(n->split_ratio, (chg == CHANGE_INCREASE ? INC_EXP : DEC_EXP));
  30 }
  31
  32 node_t *first_extrema(node_t *n)
  33 {
  34     if (n == NULL)
  35         return NULL;
  36     else if (n->first_child == NULL)
  37         return n;
  38     else
  39         return first_extrema(n->first_child);
  40 }
  41
  42 node_t *second_extrema(node_t *n)
  43 {
  44     if (n == NULL)
  45         return NULL;
  46     else if (n->second_child == NULL)
  47         return n;
  48     else
  49         return second_extrema(n->second_child);
  50 }
  51
  52 node_t *next_leaf(node_t *n)
  53 {
  54     if (n == NULL)
  55         return NULL;
  56     node_t *p = n;
  57     while (is_second_child(p))
  58         p = p->parent;
  59     if (p->parent == NULL)
  60         return NULL;
  61     return first_extrema(p->parent->second_child);
  62 }
  63
  64 node_t *prev_leaf(node_t *n)
  65 {
  66     if (n == NULL)
  67         return NULL;
  68     node_t *p = n;
  69     while (is_first_child(p))
  70         p = p->parent;
  71     if (p->parent == NULL)
  72         return NULL;
  73     return second_extrema(p->parent->first_child);
  74 }
  75
  76 node_t *find_fence(node_t *n, direction_t dir)
  77 {
  78     node_t *p;
  79
  80     if (n == NULL)
  81         return NULL;
  82
  83     p = n->parent;
  84
  85     while (p != NULL) {
  86         if ((dir == DIR_UP && p->split_type == TYPE_HORIZONTAL && p->rectangle.y < n->rectangle.y)
  87                 || (dir == DIR_LEFT && p->split_type == TYPE_VERTICAL && p->rectangle.x < n->rectangle.x)
  88                 || (dir == DIR_DOWN && p->split_type == TYPE_HORIZONTAL && (p->rectangle.y + p->rectangle.height) > (n->rectangle.y + n->rectangle.height))
  89                 || (dir == DIR_RIGHT && p->split_type == TYPE_VERTICAL && (p->rectangle.x + p->rectangle.width) > (n->rectangle.x + n->rectangle.width)))
  90             return p;
  91         p = p->parent;
  92     }
  93
  94     return NULL;
  95 }
  96
  97 node_t *find_neighbor(node_t *n, direction_t dir)
  98 {
  99     node_t *fence = find_fence(n, dir);
 100
 101     if (fence == NULL)
 102         return NULL;
 103
 104     if (dir == DIR_UP || dir == DIR_LEFT)
 105         return second_extrema(fence->first_child);
 106     else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 107         return first_extrema(fence->second_child);
 108
 109     return NULL;
 110 }
 111
 112 void move_fence(node_t *n, direction_t dir, fence_move_t mov)
 113 {
 114     node_t *fence = find_fence(n, dir);
 115
 116     if (fence == NULL)
 117         return;
 118
 119     if ((mov == MOVE_PUSH && (dir == DIR_RIGHT || dir == DIR_DOWN))
 120             || (mov == MOVE_PULL && (dir == DIR_LEFT || dir == DIR_UP)))
 121         change_split_ratio(fence, CHANGE_INCREASE);
 122     else
 123         change_split_ratio(fence, CHANGE_DECREASE);
 124 }
 125
 126
 127 void rotate_tree(node_t *n, rotate_t rot)
 128 {
 129     if (n == NULL || is_leaf(n))
 130         return;
 131
 132     node_t *tmp;
 133
 134     if ((rot == ROTATE_CLOCK_WISE && n->split_type == TYPE_HORIZONTAL)
 135             || (rot == ROTATE_COUNTER_CW && n->split_type == TYPE_VERTICAL)
 136             || rot == ROTATE_FULL_CYCLE) {
 137         tmp = n->first_child;
 138         n->first_child = n->second_child;
 139         n->second_child = tmp;
 140         n->split_ratio = 1.0 - n->split_ratio;
 141     }
 142
 143     if (rot != ROTATE_FULL_CYCLE) {
 144         if (n->split_type == TYPE_HORIZONTAL)
 145             n->split_type = TYPE_VERTICAL;
 146         else if (n->split_type == TYPE_VERTICAL)
 147             n->split_type = TYPE_HORIZONTAL;
 148     }
 149
 150     rotate_tree(n->first_child, rot);
 151     rotate_tree(n->second_child, rot);
 152 }
 153
 154 void dump_tree(node_t *n, char *rsp, int depth)
 155 {
 156     if (n == NULL)
 157         return;
 158
 159     for (int i = 0; i < depth; i++)
 160         sprintf(rsp, "%s", "  ");
 161
 162     if (n->client == NULL)
 163         sprintf(rsp, "%s %.2f\n", (n->split_type == TYPE_HORIZONTAL ? "H" : "V"), n->split_ratio);
 164     else
 165         sprintf(rsp, "%X\n", n->client->window);
 166
 167     dump_tree(n->first_child, rsp, depth + 1);
 168     dump_tree(n->second_child, rsp, depth + 1);
 169 }
 170
 171 void update_root_dimensions(void)
 172 {
 173     desktop_t *d = desk_head;
 174     while (d != NULL) {
 175         d->root->rectangle = (xcb_rectangle_t) {left_padding, top_padding, screen_width - (left_padding + right_padding), screen_height - (top_padding + bottom_padding)};
 176         d = d->next;
 177     }
 178 }
 179
 180 void apply_layout(desktop_t *d, node_t *n)
 181 {
 182     if (n == NULL)
 183         return;
 184     if (is_leaf(n)) {
 185         uint32_t values[4];
 186         xcb_rectangle_t rect;
 187         if (desk->layout == LAYOUT_TILED)
 188             rect = n->rectangle;
 189         else if (desk->layout == LAYOUT_MONOCLE)
 190             rect = d->root->rectangle;
 191         values[0] = rect.x;
 192         values[1] = rect.y;
 193         values[2] = rect.width;
 194         values[3] = rect.height;
 195         xcb_configure_window(dpy, n->client->window, MOVE_RESIZE_MASK, values);
 196     } else {
 197         unsigned int fence;
 198         xcb_rectangle_t rect = n->rectangle;
 199         if (n->split_type == TYPE_VERTICAL) {
 200             fence = rect.width * n->split_ratio;
 201             n->first_child->rectangle = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
 202             n->second_child->rectangle = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
 203
 204         } else if (n->split_type == TYPE_HORIZONTAL) {
 205             fence = rect.height * n->split_ratio;
 206             n->first_child->rectangle = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
 207             n->second_child->rectangle = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
 208         }
 209         apply_layout(d, n->first_child);
 210         apply_layout(d, n->second_child);
 211     }
 212 }
 213
 214 void insert_node(desktop_t *d, node_t *n)
 215 {
 216     if (d == NULL || n == NULL)
 217         return;
 218
 219     node_t *focus = d->focus;
 220
 221     if (focus == NULL) {
 222         d->root = n;
 223     } else {
 224         node_t *dad = make_node();
 225         node_t *fopar = focus->parent;
 226         n->parent = dad;
 227         switch (split_mode) {
 228             case MODE_AUTOMATIC:
 229                 if (fopar == NULL) {
 230                     dad->first_child = n;
 231                     dad->second_child = focus;
 232                     dad->split_type = TYPE_VERTICAL;
 233                     focus->parent = dad;
 234                     d->root = dad;
 235                 } else {
 236                     node_t *grandpa = fopar->parent;
 237                     dad->parent = grandpa;
 238                     if (grandpa != NULL) {
 239                         if (is_first_child(fopar))
 240                             grandpa->first_child = dad;
 241                         else
 242                             grandpa->second_child = dad;
 243                     } else {
 244                         d->root = dad;
 245                     }
 246                     dad->split_type = fopar->split_type;
 247                     dad->split_ratio = fopar->split_ratio;
 248                     fopar->parent = dad;
 249                     if (is_first_child(focus)) {
 250                         dad->first_child = n;
 251                         dad->second_child = fopar;
 252                         rotate_tree(fopar, ROTATE_CLOCK_WISE);
 253                     } else {
 254                         dad->first_child = fopar;
 255                         dad->second_child = n;
 256                         rotate_tree(fopar, ROTATE_COUNTER_CW);
 257                     }
 258                 }
 259                 break;
 260             case MODE_MANUAL:
 261                 focus->parent = dad;
 262                 switch (split_dir) {
 263                     case DIR_LEFT:
 264                     dad->split_type = TYPE_VERTICAL;
 265                     dad->first_child = n;
 266                     dad->second_child = focus;
 267                     break;
 268                     case DIR_RIGHT:
 269                     dad->split_type = TYPE_VERTICAL;
 270                     dad->first_child = focus;
 271                     dad->second_child = n;
 272                     break;
 273                     case DIR_UP:
 274                     dad->split_type = TYPE_HORIZONTAL;
 275                     dad->first_child = n;
 276                     dad->second_child = focus;
 277                     break;
 278                     case DIR_DOWN:
 279                     dad->split_type = TYPE_HORIZONTAL;
 280                     dad->first_child = focus;
 281                     dad->second_child = n;
 282                     break;
 283                 }
 284                 if (d->root == focus)
 285                     d->root = dad;
 286                 split_mode = MODE_AUTOMATIC;
 287                 break;
 288         }
 289     }
 290 }
 291
 292 void focus_node(desktop_t *d, node_t *n)
 293 {
 294     if (d == NULL || n == NULL || d->focus == n)
 295         return;
 296
 297     draw_triple_border(d->focus, normal_border_color_pxl);
 298     draw_triple_border(n, active_border_color_pxl);
 299
 300     xcb_set_input_focus(dpy, XCB_INPUT_FOCUS_POINTER_ROOT, n->client->window, XCB_CURRENT_TIME);
 301 }
 302
 303 void select_desktop(desktop_t *d)
 304 {
 305     if (d == NULL)
 306         return;
 307 }