openbox/client_time_heap.c

   1 /* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*-
   2
   3    client_time_heap.c for the Openbox window manager
   4    Copyright (c) 2006        Mikael Magnusson
   5    Copyright (c) 2003-2007   Dana Jansens
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    See the COPYING file for a copy of the GNU General Public License.
  18 */
  19
  20 #include "client_time_heap.h"
  21 #include "client.h"
  22
  23 #include <X11/Xlib.h>
  24
  25 /* Helper functions for the heap */
  26
  27 #define isroot(n) (n == 0)
  28 #define parent(n) ((n-1)/2)
  29 #define right(n) ((n+1)*2)
  30 #define left(n) (right(n)-1)
  31 #define exists(n) (n < h->nodes->len)
  32 #define key(n) (((ObClient*)h->nodes->pdata[n])->user_time)
  33
  34 static inline void swap(ObClientTimeHeap *h, guint a, guint b)
  35 {
  36     gpointer c;
  37
  38     g_assert(a < h->nodes->len);
  39     g_assert(b < h->nodes->len);
  40
  41     c = h->nodes->pdata[a];
  42     h->nodes->pdata[a] = h->nodes->pdata[b];
  43     h->nodes->pdata[b] = c;
  44 }
  45
  46 static inline void heapify(ObClientTimeHeap *h, guint n)
  47 {
  48     g_assert(exists(n));
  49
  50     /* fix up the heap, move it down below keys it's smaller than */
  51     while ((exists(left(n)) && key(n) < key(left(n))) ||
  52            (exists(right(n)) && key(n) < key(right(n))))
  53     {
  54         if (exists(left(n)) && exists(right(n)))
  55             if (key(left(n)) > key(right(n))) {
  56                 swap(h, n, left(n));
  57                 n = left(n);
  58             } else {
  59                 swap(h, n, right(n));
  60                 n = right(n);
  61             }
  62         else {
  63             /* its impossible in this structure to have a right child but no
  64                left child */
  65             swap(h, n, left(n));
  66             n = left(n);
  67         }
  68     }
  69 }
  70
  71 ObClientTimeHeap* client_time_heap_new()
  72 {
  73     ObClientTimeHeap *h = g_new0(ObClientTimeHeap, 1);
  74     h->nodes = g_ptr_array_new();
  75     return h;
  76 }
  77
  78 void client_time_heap_free(ObClientTimeHeap *h)
  79 {
  80     if (h != NULL) {
  81         /* all the clients should be removed before the heap is destroyed. */
  82         g_assert(h->nodes->len == 0);
  83         g_ptr_array_free(h->nodes, TRUE);
  84         g_free(h);
  85     }
  86 }
  87
  88 guint32 client_time_heap_maximum(ObClientTimeHeap *h)
  89 {
  90     if (h->nodes->len == 0)
  91         return CurrentTime;
  92     else
  93         return key(0);
  94 }
  95
  96
  97 void client_time_heap_add(ObClientTimeHeap *h, ObClient *c)
  98 {
  99     guint n;
 100
 101     /* insert it as the last leaf */
 102     g_ptr_array_add(h->nodes, c);
 103     n = h->nodes->len - 1;
 104
 105     /* move it up to its proper place */
 106     while (!isroot(n) && key(n) > key(parent(n))) {
 107         swap(h, n, parent(n));
 108         n = parent(n);
 109     }
 110 }
 111
 112 void client_time_heap_remove(ObClientTimeHeap *h, ObClient *c)
 113 {
 114     /* find the client */
 115     guint n;
 116     for (n = 0; h->nodes->pdata[n] != c && n < h->nodes->len; ++n);
 117
 118     /* if the client is in the heap */
 119     if (n < h->nodes->len) {
 120         /* move it to a leaf and delete it from the heap */
 121         swap(h, n, h->nodes->len-1);
 122         g_ptr_array_remove_index(h->nodes, h->nodes->len-1);
 123
 124         /* move the swapped leaf down to its proper place if it wasn't just
 125            deleted */
 126         if (exists(n))
 127             heapify(h, n);
 128     }
 129 }
 130
 131 void client_time_heap_decrease_key(ObClientTimeHeap *h, ObClient *c)
 132 {
 133     /* find the client */
 134     guint n;
 135     for (n = 0; h->nodes->pdata[n] != c && n < h->nodes->len; ++n);
 136
 137     /* if the client is in the heap */
 138     if (n < h->nodes->len) {
 139         /* move it down to its proper place */
 140         heapify(h, n);
 141     }
 142 }
 143
 144 void client_time_heap_increase_key(ObClientTimeHeap *h, ObClient *c)
 145 {
 146     /* find the client */
 147     guint n;
 148     for (n = 0; h->nodes->pdata[n] != c && n < h->nodes->len; ++n);
 149
 150     /* if the client is in the heap */
 151     if (n < h->nodes->len) {
 152         /* move it up to its proper place */
 153         while (!isroot(n) && key(n) > key(parent(n))) {
 154             swap(h, n, parent(n));
 155             n = parent(n);
 156         }
 157     }
 158 }