src/history.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 <stdlib.h>
  26 #include <stdbool.h>
  27 #include "bspwm.h"
  28 #include "tree.h"
  29 #include "query.h"
  30 #include "history.h"
  31
  32 history_t *make_history(monitor_t *m, desktop_t *d, node_t *n)
  33 {
  34         history_t *h = calloc(1, sizeof(history_t));
  35         h->loc = (coordinates_t) {m, d, n};
  36         h->prev = h->next = NULL;
  37         h->latest = true;
  38         return h;
  39 }
  40
  41 void history_add(monitor_t *m, desktop_t *d, node_t *n, bool focused)
  42 {
  43         if (!record_history) {
  44                 return;
  45         }
  46
  47         if (focused) {
  48                 history_needle = NULL;
  49         }
  50
  51         history_t *h = make_history(m, d, n);
  52
  53         if (history_head == NULL) {
  54                 history_head = history_tail = h;
  55         } else if ((n != NULL && history_tail->loc.node != n) || (n == NULL && d != history_tail->loc.desktop)) {
  56                 history_t *ip = focused ? history_tail : NULL;
  57
  58                 for (history_t *hh = history_tail; hh != NULL; hh = hh->prev) {
  59                         if ((n != NULL && hh->loc.node == n) || (n == NULL && d == hh->loc.desktop)) {
  60                                 hh->latest = false;
  61                         }
  62                         if (ip == NULL && ((n != NULL && hh->loc.desktop == d) || (n == NULL && hh->loc.monitor == m))) {
  63                                 ip = hh;
  64                         }
  65                 }
  66
  67                 if (ip != NULL) {
  68                         history_insert_after(h, ip);
  69                 } else {
  70                         ip = history_head;
  71                         if (n != NULL) {
  72                                 for (history_t *hh = history_head; hh != NULL; hh = hh->next) {
  73                                         if (hh->latest && hh->loc.monitor == m) {
  74                                                 ip = hh;
  75                                                 break;
  76                                         }
  77                                 }
  78                         }
  79                         history_insert_before(h, ip);
  80                 }
  81         } else {
  82                 free(h);
  83         }
  84 }
  85
  86 // Inserts `a` after `b`.
  87 void history_insert_after(history_t *a, history_t *b)
  88 {
  89         a->next = b->next;
  90         if (b->next != NULL) {
  91                 b->next->prev = a;
  92         }
  93         b->next = a;
  94         a->prev = b;
  95         if (history_tail == b) {
  96                 history_tail = a;
  97         }
  98 }
  99
 100 // Inserts `a` before `b`.
 101 void history_insert_before(history_t *a, history_t *b)
 102 {
 103         a->prev = b->prev;
 104         if (b->prev != NULL) {
 105                 b->prev->next = a;
 106         }
 107         b->prev = a;
 108         a->next = b;
 109         if (history_head == b) {
 110                 history_head = a;
 111         }
 112 }
 113
 114 void history_remove(desktop_t *d, node_t *n, bool deep)
 115 {
 116         /* removing from the newest to the oldest is required */
 117         /* for maintaining the *latest* attribute */
 118         history_t *b = history_tail;
 119         while (b != NULL) {
 120                 if ((n != NULL && ((deep && is_descendant(b->loc.node, n)) || (!deep && b->loc.node == n))) ||
 121                     (n == NULL && d == b->loc.desktop)) {
 122                         history_t *a = b->next;
 123                         history_t *c = b->prev;
 124                         if (a != NULL) {
 125                                 /* remove duplicate entries */
 126                                 while (c != NULL && ((a->loc.node != NULL && a->loc.node == c->loc.node) ||
 127                                        (a->loc.node == NULL && a->loc.desktop == c->loc.desktop))) {
 128                                         history_t *p = c->prev;
 129                                         if (history_head == c) {
 130                                                 history_head = history_tail;
 131                                         }
 132                                         if (history_needle == c) {
 133                                                 history_needle = history_tail;
 134                                         }
 135                                         free(c);
 136                                         c = p;
 137                                 }
 138                                 a->prev = c;
 139                         }
 140                         if (c != NULL) {
 141                                 c->next = a;
 142                         }
 143                         if (history_tail == b) {
 144                                 history_tail = c;
 145                         }
 146                         if (history_head == b) {
 147                                 history_head = a;
 148                         }
 149                         if (history_needle == b) {
 150                                 history_needle = c;
 151                         }
 152                         free(b);
 153                         b = c;
 154                 } else {
 155                         b = b->prev;
 156                 }
 157         }
 158 }
 159
 160 void empty_history(void)
 161 {
 162         history_t *h = history_head;
 163         while (h != NULL) {
 164                 history_t *next = h->next;
 165                 free(h);
 166                 h = next;
 167         }
 168         history_head = history_tail = NULL;
 169 }
 170
 171 node_t *history_last_node(desktop_t *d, node_t *n)
 172 {
 173         for (history_t *h = history_tail; h != NULL; h = h->prev) {
 174                 if (h->latest && h->loc.node != NULL && !h->loc.node->hidden &&
 175                     !is_descendant(h->loc.node, n) && h->loc.desktop == d) {
 176                         return h->loc.node;
 177                 }
 178         }
 179         return NULL;
 180 }
 181
 182 desktop_t *history_last_desktop(monitor_t *m, desktop_t *d)
 183 {
 184         for (history_t *h = history_tail; h != NULL; h = h->prev) {
 185                 if (h->latest && h->loc.desktop != d && h->loc.monitor == m) {
 186                         return h->loc.desktop;
 187                 }
 188         }
 189         return NULL;
 190 }
 191
 192 monitor_t *history_last_monitor(monitor_t *m)
 193 {
 194         for (history_t *h = history_tail; h != NULL; h = h->prev) {
 195                 if (h->latest && h->loc.monitor != m) {
 196                         return h->loc.monitor;
 197                 }
 198         }
 199         return NULL;
 200 }
 201
 202 bool history_find_newest_node(coordinates_t *ref, coordinates_t *dst, node_select_t *sel)
 203 {
 204         for (history_t *h = history_tail; h != NULL; h = h->prev) {
 205                 if (h->loc.node == NULL ||
 206                     h->loc.node->hidden ||
 207                     !node_matches(&h->loc, ref, sel)) {
 208                         continue;
 209                 }
 210                 *dst = h->loc;
 211                 return true;
 212         }
 213
 214         return false;
 215 }
 216
 217 bool history_find_node(history_dir_t hdi, coordinates_t *ref, coordinates_t *dst, node_select_t *sel)
 218 {
 219         if (history_needle == NULL || record_history) {
 220                 history_needle = history_tail;
 221         }
 222
 223         history_t *h;
 224         for (h = history_needle; h != NULL; h = (hdi == HISTORY_OLDER ? h->prev : h->next)) {
 225                 if (!h->latest ||
 226                     h->loc.node == NULL ||
 227                     h->loc.node == ref->node ||
 228                     h->loc.node->hidden ||
 229                     !node_matches(&h->loc, ref, sel)) {
 230                         continue;
 231                 }
 232                 if (!record_history) {
 233                         history_needle = h;
 234                 }
 235                 *dst = h->loc;
 236                 return true;
 237         }
 238         return false;
 239 }
 240
 241 bool history_find_newest_desktop(coordinates_t *ref, coordinates_t *dst, desktop_select_t *sel)
 242 {
 243         for (history_t *h = history_tail; h != NULL; h = h->prev) {
 244                 if (desktop_matches(&h->loc, ref, sel)) {
 245                         *dst = h->loc;
 246                         return true;
 247                 }
 248         }
 249
 250         return false;
 251 }
 252
 253 bool history_find_desktop(history_dir_t hdi, coordinates_t *ref, coordinates_t *dst, desktop_select_t *sel)
 254 {
 255         if (history_needle == NULL || record_history) {
 256                 history_needle = history_tail;
 257         }
 258
 259         history_t *h;
 260         for (h = history_needle; h != NULL; h = (hdi == HISTORY_OLDER ? h->prev : h->next)) {
 261                 if (!h->latest ||
 262                     h->loc.desktop == ref->desktop ||
 263                     !desktop_matches(&h->loc, ref, sel)) {
 264                         continue;
 265                 }
 266                 if (!record_history) {
 267                         history_needle = h;
 268                 }
 269                 *dst = h->loc;
 270                 return true;
 271         }
 272         return false;
 273 }
 274
 275 bool history_find_newest_monitor(coordinates_t *ref, coordinates_t *dst, monitor_select_t *sel)
 276 {
 277         for (history_t *h = history_tail; h != NULL; h = h->prev) {
 278                 if (monitor_matches(&h->loc, ref, sel)) {
 279                         *dst = h->loc;
 280                         return true;
 281                 }
 282         }
 283
 284         return false;
 285 }
 286
 287 bool history_find_monitor(history_dir_t hdi, coordinates_t *ref, coordinates_t *dst, monitor_select_t *sel)
 288 {
 289         if (history_needle == NULL || record_history) {
 290                 history_needle = history_tail;
 291         }
 292
 293         history_t *h;
 294
 295         for (h = history_needle; h != NULL; h = (hdi == HISTORY_OLDER ? h->prev : h->next)) {
 296                 if (!h->latest ||
 297                     h->loc.monitor == ref->monitor ||
 298                     !monitor_matches(&h->loc, ref, sel)) {
 299                         continue;
 300                 }
 301                 if (!record_history) {
 302                         history_needle = h;
 303                 }
 304                 *dst = h->loc;
 305                 return true;
 306         }
 307
 308         return false;
 309 }
 310
 311 uint32_t history_rank(node_t *n)
 312 {
 313         uint32_t r = 0;
 314         history_t *h = history_tail;
 315         while (h != NULL && (!h->latest || h->loc.node != n)) {
 316                 h = h->prev;
 317                 r++;
 318         }
 319         if (h == NULL) {
 320                 return UINT32_MAX;
 321         } else {
 322                 return r;
 323         }
 324 }