]>
Dogcows Code - chaz/openbox/blob - openbox/client_time_heap.c
1adefdd0ddb1bc16cf2a0ebcffa639cd6493ce09
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
));
This page took 0.039432 seconds and 3 git commands to generate.