1 /* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*-
3 client_time_heap.c for the Openbox window manager
4 Copyright (c) 2006 Mikael Magnusson
5 Copyright (c) 2003-2007 Dana Jansens
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.
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.
17 See the COPYING file for a copy of the GNU General Public License.
20 #include "client_time_heap.h"
25 /* Helper functions for the heap */
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)
34 static inline void swap(ObClientTimeHeap *h, guint a, guint b)
38 g_assert(a < h->nodes->len);
39 g_assert(b < h->nodes->len);
41 c = h->nodes->pdata[a];
42 h->nodes->pdata[a] = h->nodes->pdata[b];
43 h->nodes->pdata[b] = c;
46 static inline void heapify(ObClientTimeHeap *h, guint n)
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))))
54 if (exists(left(n)) && exists(right(n)))
55 if (key(left(n)) > key(right(n))) {
63 /* its impossible in this structure to have a right child but no
71 ObClientTimeHeap* client_time_heap_new()
73 ObClientTimeHeap *h = g_new0(ObClientTimeHeap, 1);
74 h->nodes = g_ptr_array_new();
78 void client_time_heap_free(ObClientTimeHeap *h)
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);
88 guint32 client_time_heap_maximum(ObClientTimeHeap *h)
90 if (h->nodes->len == 0)
97 void client_time_heap_add(ObClientTimeHeap *h, ObClient *c)
101 /* insert it as the last leaf */
102 g_ptr_array_add(h->nodes, c);
103 n = h->nodes->len - 1;
105 /* move it up to its proper place */
106 while (!isroot(n) && key(n) > key(parent(n))) {
107 swap(h, n, parent(n));
112 void client_time_heap_remove(ObClientTimeHeap *h, ObClient *c)
114 /* find the client */
116 for (n = 0; h->nodes->pdata[n] != c && n < h->nodes->len; ++n);
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);
124 /* move the swapped leaf down to its proper place if it wasn't just
131 void client_time_heap_decrease_key(ObClientTimeHeap *h, ObClient *c)
133 /* find the client */
135 for (n = 0; h->nodes->pdata[n] != c && n < h->nodes->len; ++n);
137 /* if the client is in the heap */
138 if (n < h->nodes->len) {
139 /* move it down to its proper place */
144 void client_time_heap_increase_key(ObClientTimeHeap *h, ObClient *c)
146 /* find the client */
148 for (n = 0; h->nodes->pdata[n] != c && n < h->nodes->len; ++n);
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));