su  1.12.11devel
 All Data Structures Files Functions Variables Typedefs Enumerator Macros Groups Pages
heap.h
Go to the documentation of this file.
1 /*
2  * This file is part of the Sofia-SIP package
3  *
4  * Copyright (C) 2007 Nokia Corporation.
5  *
6  * Contact: Pekka Pessi <pekka.pessi@nokia-email.address.hidden>
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation; either version 2.1 of
11  * the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful, but
14  * WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with this library; if not, write to the Free Software
20  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
21  * 02110-1301 USA
22  *
23  */
24 
25 #ifndef SOFIA_SIP_HEAP_H
26 
27 #define SOFIA_SIP_HEAP_H
28 
77 #define HEAP_MIN_SIZE 31
78 
85 #define HEAP_TYPE struct { void *private; }
86 
111 #define HEAP_DECLARE(scope, heaptype, prefix, type) \
112 scope int prefix##resize(void *, heaptype *, size_t); \
113 scope int prefix##free(void *, heaptype *); \
114 scope int prefix##is_full(heaptype const); \
115 scope size_t prefix##size(heaptype const); \
116 scope size_t prefix##used(heaptype const); \
117 scope void prefix##sort(heaptype); \
118 scope int prefix##add(heaptype, type); \
119 scope type prefix##remove(heaptype, size_t); \
120 scope type prefix##get(heaptype, size_t)
121 
162 #define HEAP_BODIES(scope, heaptype, prefix, type, less, set, alloc, null) \
163 scope int prefix##resize(void *realloc_arg, heaptype h[1], size_t new_size) \
164 { \
165  struct prefix##priv { size_t _size, _used; type _heap[2]; }; \
166  struct prefix##priv *_priv; \
167  size_t _offset = \
168  (offsetof(struct prefix##priv, _heap[1]) - 1) / sizeof (type); \
169  size_t _min_size = 32 - _offset; \
170  size_t _bytes; \
171  size_t _used = 0; \
172  \
173  _priv = *(void **)h; \
174  \
175  if (_priv) { \
176  if (new_size == 0) \
177  new_size = 2 * _priv->_size + _offset + 1; \
178  _used = _priv->_used; \
179  if (new_size < _used) \
180  new_size = _used; \
181  } \
182  \
183  if (new_size < _min_size) \
184  new_size = _min_size; \
185  \
186  _bytes = (_offset + 1 + new_size) * sizeof (type); \
187  \
188  (void)realloc_arg; /* avoid warning */ \
189  _priv = alloc(realloc_arg, *(struct prefix##priv **)h, _bytes); \
190  if (!_priv) \
191  return -1; \
192  \
193  *(struct prefix##priv **)h = _priv; \
194  _priv->_size = new_size; \
195  _priv->_used = _used; \
196  \
197  return 0; \
198 } \
199  \
200  \
201 scope int prefix##free(void *realloc_arg, heaptype h[1]) \
202 { \
203  (void)realloc_arg; \
204  *(void **)h = alloc(realloc_arg, *(void **)h, 0); \
205  return 0; \
206 } \
207  \
208  \
209 scope int prefix##is_full(heaptype h) \
210 { \
211  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
212  struct prefix##priv *_priv = *(void **)&h; \
213  \
214  return _priv == NULL || _priv->_used >= _priv->_size; \
215 } \
216  \
217  \
218 scope int prefix##add(heaptype h, type e) \
219 { \
220  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
221  struct prefix##priv *_priv = *(void **)&h; \
222  type *heap = _priv->_heap - 1; \
223  size_t i, parent; \
224  \
225  if (_priv == NULL || _priv->_used >= _priv->_size) \
226  return -1; \
227  \
228  for (i = ++_priv->_used; i > 1; i = parent) { \
229  parent = i / 2; \
230  if (!less(e, heap[parent])) \
231  break; \
232  set(heap, i, heap[parent]); \
233  } \
234  \
235  set(heap, i, e); \
236  \
237  return 0; \
238 } \
239  \
240  \
241 scope type prefix##remove(heaptype h, size_t index) \
242 { \
243  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
244  struct prefix##priv *_priv = *(void **)&h; \
245  type *heap = _priv->_heap - 1; \
246  type retval[1]; \
247  type e; \
248  \
249  size_t top, left, right, move; \
250  \
251  if (index - 1 >= _priv->_used) \
252  return (null); \
253  \
254  move = _priv->_used--; \
255  set(retval, 0, heap[index]); \
256  \
257  for (top = index;;index = top) { \
258  left = 2 * top; \
259  right = 2 * top + 1; \
260  \
261  if (left >= move) \
262  break; \
263  if (right < move && less(heap[right], heap[left])) \
264  top = right; \
265  else \
266  top = left; \
267  set(heap, index, heap[top]); \
268  } \
269  \
270  if (index == move) \
271  return *retval; \
272  \
273  e = heap[move]; \
274  for (; index > 1; index = top) { \
275  top = index / 2; \
276  if (!less(e, heap[top])) \
277  break; \
278  set(heap, index, heap[top]); \
279  } \
280  \
281  set(heap, index, e); \
282  \
283  return *retval; \
284 } \
285  \
286 scope \
287 type prefix##get(heaptype h, size_t index) \
288 { \
289  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
290  struct prefix##priv *_priv = *(void **)&h; \
291  \
292  if (--index >= _priv->_used) \
293  return (null); \
294  \
295  return _priv->_heap[index]; \
296 } \
297  \
298 scope \
299 size_t prefix##size(heaptype const h) \
300 { \
301  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
302  struct prefix##priv *_priv = *(void **)&h; \
303  return _priv ? _priv->_size : 0; \
304 } \
305  \
306 scope \
307 size_t prefix##used(heaptype const h) \
308 { \
309  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
310  struct prefix##priv *_priv = *(void **)&h; \
311  return _priv ? _priv->_used : 0; \
312 } \
313 static int prefix##_less(void *h, size_t a, size_t b) \
314 { \
315  type *_heap = h; return less(_heap[a], _heap[b]); \
316 } \
317 static void prefix##_swap(void *h, size_t a, size_t b) \
318 { \
319  type *_heap = h; type _swap = _heap[a]; \
320  set(_heap, a, _heap[b]); set(_heap, b, _swap); \
321 } \
322 scope void prefix##sort(heaptype h) \
323 { \
324  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
325  struct prefix##priv *_priv = *(void **)&h; \
326  if (_priv) \
327  su_smoothsort(_priv->_heap - 1, 1, _priv->_used, prefix##_less, prefix##_swap); \
328 } \
329 extern int const prefix##dummy_heap
330 
331 #include <sofia-sip/su_types.h>
332 
333 SOFIA_BEGIN_DECLS
334 
335 SOFIAPUBFUN void su_smoothsort(void *base, size_t r0, size_t N,
336  int (*less)(void *base, size_t a, size_t b),
337  void (*swap)(void *base, size_t a, size_t b));
338 
339 SOFIA_END_DECLS
340 
341 #endif

Sofia-SIP 1.12.11devel - Copyright (C) 2006 Nokia Corporation. All rights reserved. Licensed under the terms of the GNU Lesser General Public License.