get rid of global client_last_user_time variable.
[dana/openbox.git] / 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 }